HackerRank Strings: Making Anagrams

Patrick
Patrick
Aug 9, 2017 · 2 min read

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:

Patrick

Written by

Software engineer. Posting some random notes here.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade