HackerRank Strings: Making Anagrams
Problem Link: https://www.hackerrank.com/challenges/ctci-making-anagrams
Solution 1:
The problem already has the constraints that all the characters are lowercase. To solve this problem, we just need to count each character’s occurrence in each string and find the difference between their counts.
So we already know there are only 26 lowercase characters, an array should be easy enough to count the occurrence.
Please note that character could be casted to their ascii value this way:
int asciiVal = (int) ‘a’; // asciiVal=97 here Here is the complete solution:
public static int numberNeeded(String first, String second) {
//check corner case
if (first.length() == 0 || second.length() == 0) {
return first.length() == 0 ? second.length() : first.length();
}
char[] firstChars = first.toCharArray();
char[] secondChars = second.toCharArray();
int[] firstHelper = new int[26];
int[] secondHelper = new int[26];
int aVal = (int) 'a', sum = 0;
for (int i = 0; i < firstChars.length; i++) {
firstHelper[(int) firstChars[i] - aVal] += 1;
}
for (int i = 0; i < secondChars.length; i++) {
secondHelper[(int) secondChars[i] - aVal] += 1;
}
for (int i = 0; i < 26; i++) {
if (firstHelper[i] != secondHelper[i]) {
sum += Math.abs(firstHelper[i] - secondHelper[i]);
}
}
return sum;
}Time Complexity: O(max(a.length(), b.length())
Solution 2:
How to improve the code in solution 1? Well, we can reduce the space complexity and use the new Feature from Java8:
public static int numberNeeded2(String first, String second) {
if (first.length() == 0 || second.length() == 0) {
return first.length() == 0 ? second.length() : first.length();
}
int result = 0;
int[] letters = new int[26];
for (char c : first.toCharArray()) {
letters[c - 'a']++;
}
for (char c : second.toCharArray()) {
letters[c - 'a']--;
}
for (int i : letters) {
result += Math.abs(i);
}
return result;
}Although it still has three for loops, helper array is reduced to only one. The new iteration in Java is really handy!
Time Complexity: O(max(a.length(), b.length())
Source Code:
