In this post we will solve the LeetCode 1347 Minimum Number of Steps to Make Two Strings Anagram problem using Java.
You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character. Return the minimum number of steps to make t an anagram of s. An Anagram of a string is a string that contains the same characters with a different (or the same) ordering. Constraints: o 1 <= s.length <= 5 * 10^4 o s.length == t.length o s and t consist of lowercase English letters only. Related Topics: o Hash Table o String
It seems that in this problem it is needed to replace the minimum number of characters in string `t` with lowercase characters from the English alphabet in order to make `t` an anagram of string `s`.
It took me some time to go from the description of the problem provided by LeetCode to what I wrote in the previous paragraph. That said; for this or any other problem on any website, you should always read and understand what is required before coding a solution.
As previously stated, I will be solving the problem using the Java programming language and the VSCode IDE on a Windows computer. My suggestion to you is to solve the problem directly on the website using the online IDE provided by LeetCode.
I will be solving the problem on my computer and then copying to the LeetCode web site for evaluation. The reason for this is to have test code readily available on a computer in my local network. For this reason I will be generating some simple test code. Please note that such code IS NOT PART OF THE SOLUTION!
public int minSteps(String s, String t) {
}
The signature for the function of interest provides us with the two strings. As stated in the requirements, the strings are of the same length and they have at least one character.
bab aba main <<< s ==>bab<== main <<< t ==>aba<== <<< arrS: [1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< arrT: [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< diffs: 2 main <<< minSteps0: 1 <<< freqS: [1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< freqT: [2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< ch: b count: 1 main <<< minSteps: 1 leetcode practice main <<< s ==>leetcode<== main <<< t ==>practice<== <<< arrS: [0, 0, 1, 1, 3, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] <<< arrT: [1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0] <<< diffs: 10 main <<< minSteps0: 5 <<< freqS: [0, 0, 1, 1, 3, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] <<< freqT: [1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0] <<< ch: d count: 1 <<< ch: e count: 2 <<< ch: l count: 1 <<< ch: o count: 1 main <<< minSteps: 5 anagram mangaar main <<< s ==>anagram<== main <<< t ==>mangaar<== <<< arrS: [3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] <<< arrT: [3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] <<< diffs: 0 main <<< minSteps0: 0 <<< freqS: [3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] <<< freqT: [3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] main <<< minSteps: 0 cake bake main <<< s ==>cake<== main <<< t ==>bake<== <<< arrS: [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< arrT: [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< diffs: 2 main <<< minSteps0: 1 <<< freqS: [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< freqT: [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< ch: c count: 1 main <<< minSteps: 1 babe cake main <<< s ==>babe<== main <<< t ==>cake<== <<< arrS: [1, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< arrT: [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< diffs: 4 main <<< minSteps0: 2 <<< freqS: [1, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< freqT: [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] <<< ch: b count: 2 main <<< minSteps: 2
Each test case is separated from the next by two blank lines.
The first two input lines hold the values for the strings `s` and `t` respectively.
Our test scaffold seems to read both input lines, assign the values to the respective strings, and then display them for us to verify that all is well so far.
I wrote two similar versions of the function of interest. The first one I did under time constraints.
The test code invokes the implementations which display intermediate values. The returning results are displayed by the test scaffold. In between the call of an implementation and the result are statements that display intermediate values for us to follow the algorithm. I commented out such statements when the submissions for evaluation at LeetCode were made. I believe you could leave them in but they will dramatically slow down execution.
/**
* Test scaffold.
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read `s` ****
String s = br.readLine().trim();
// **** read `t` ****
String t = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< s ==>" + s + "<==");
System.out.println("main <<< t ==>" + t + "<==");
// **** call function of interest and display result ****
System.out.println("main <<< minSteps0: " + minSteps0(s, t));
// **** call function of interest and display result ****
System.out.println("main <<< minSteps: " + minSteps(s, t));
}
This code represents the test scaffold I wrote for this problem. It is NOT PART OF THE SOLUTION.
I used a buffered reader to read the two input lines. The values of the strings are displayed so we may visually check that all is well so far. The test code then calls the two implementations of the function of interest which are quite similar as we will shortly find out.
/**
* Return the minimum number of steps to make t an anagram of s.
*
* Using arrays.
*
* Execution: O(n) - Space: O(K)
*
* Runtime: 10 ms, faster than 83.37% of Java online submissions.
* Memory Usage: 52 MB, less than 6.04% of Java online submissions.
*
* 63 / 63 test cases passed.
* Status: Accepted
* Runtime: 10 ms
* Memory Usage: 52 MB
*/
static public int minSteps0(String s, String t) {
// **** initialization ****
int diffs = 0;
int[] arrS = new int[26];
int[] arrT = new int[26];
// **** get character counts from `s` - O(n) ****
for (char c : s.toCharArray())
arrS++;
// **** get character counts from `t` - O(n) ****
for (char c : t.toCharArray())
arrT++;
// ???? ????
System.out.println("<<< arrS: " + Arrays.toString(arrS));
System.out.println("<<< arrT: " + Arrays.toString(arrT));
// **** traverse both array counting differences - O(K) ****
for (int i = 0; i < 26; i++) {
// **** compute diff ****
// diffs += Math.abs(arrS[i] - arrT[i]);
int diff = arrS[i] - arrT[i];
// **** update diffs ****
if (diff < 0) diffs += -diff;
else if (diff > 0) diffs += diff;
}
// ???? ????
System.out.println("<<< diffs: " + diffs);
// **** return number of steps ****
return diffs / 2;
}
The function starts by initializing the `diffs` variable which is used to count the number of different characters we need to replace in the string `t`. We declare a couple int[] arrays to keep track of the frequencies of characters in the strings. There are 26 lowercase characters in the English alphabet.
We then traverse the characters in string `s` and update the frequencies in the associated array. The same is done for string `t`.
The next loop is used to traverse the char[] arrays and compute the differences in frequencies and add them to the `diffs` variable.
When done the result is returned.
Please take a look at the comments section of this implementation. Execution took 10 milliseconds.
/**
* Return the minimum number of steps to make t an anagram of s.
*
* Using arrays.
*
* Execution: O(n) - Space: O(K)
*
* Runtime: 10 ms, faster than 83.37% of Java online submissions.
* Memory Usage: 39.3 MB, less than 92.36% of Java online submissions.
*
* 63 / 63 test cases passed.
* Status: Accepted
* Runtime: 10 ms
* Memory Usage: 39.3 MB
*/
static public int minSteps(String s, String t) {
// **** initialization ****
int steps = 0; // should be count of letters to be replaced
int[] freqS = new int[26];
int[] freqT = new int[26];
char[] chS = s.toCharArray();
char[] chT = t.toCharArray();
// **** get character frequencies from `s` and `t` - O(n) ****
for (int i = 0; i < s.length(); i++) {
freqS[chS[i] - 'a']++;
freqT[chT[i] - 'a']++;
}
// ???? ????
System.out.println("<<< freqS: " + Arrays.toString(freqS));
System.out.println("<<< freqT: " + Arrays.toString(freqT));
// **** count number of letters to be replaced in `t` - O(K) ****
for (int i = 0; i < 26; i++) {
if (freqS[i] > freqT[i]) {
// ???? ????
System.out.println("<<< ch: " + (char)('a' + i) + " count: " + (freqS[i] - freqT[i]));
// **** count of this letter in `s` to replace in `t` ****
steps += freqS[i] - freqT[i];
}
}
// **** return number of steps (or letters to be replaced in `t` ****
return steps;
}
This is the second implementation of the function of interest. It is quite similar to the previous one due to the fact that I just tried to optimize it.
The first loop populates both frequencies in the int[] arrays instead of using two different loops.
By looking at the arrays with the character frequencies, it becomes clear that instead of adding the differences between strings and then dividing the result, we may update the number of steps when needed based on the values of the corresponding frequencies per character.
When the loop completes, we just return the number of steps (no need to divide by 2 as we did in the previous implementation).
Please take a look at the comments section of this implementation. Of interest is that the execution time of 10 ms is the same as in the previous implementation.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named MinNumOfStepsToMakeTwoStringsAnagram.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John