Anagrams

Write a method isAnagram that checks if two lowercase input Strings are anagrams of each other. An anagram of a String is a String that is formed by simply re-arranging its letters, using each letter exactly once. Your algorithm should run in linear O(n) time and use constant O(1) space.

Examples:

isAnagram("abc","cab") => true
isAnagram("b","b") => true
isAnagram("bd","cb") => false

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

This is a fairly straightforward problem - and can be solved in multiple ways. But hold on! Look at the constraints. A linear runtime of O(n) means that you cannot simply sort the two Strings and compare them. So let's rule out sorting, as not even the best sorting algorithms can achieve a linear runtime complexity. Let's take a look at the Space requirement. A constant space of O(1) doesn't mean you cannot use any space! It simply means that the amount of space you use should not grow with the input.

A more detailed explanation

Since there are only 26 alphabets in English, we can use a constant size buffer to record all instances of alphabets in the 2 Strings. The number of times an alphabet appears in the 2 Strings should be the same.

How do you convert an ASCII lowercase alphabet to its 0 - 25 counterpart in english? - buffer[input1.charAt(i) - 'a']

Final hint! You should be able to code the problem on viewing this.

1) Create a constant size array os 26 integers - int[] buffer = new int[256]

2) Sweep across the first String and mark the positions of the characters encountered in the buffer by incrementing the respective index by 1 - buffer[charPosition]++

3) Sweep across the second String, but this time decrement the index. buffer[charPosition]--

4) Iterate over the constant size buffer and check each index. If every index == 0, the two Strings are anagrams of each other!

public static boolean isAnagram(String input1, String input2) {
    
}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Anagrams

Quick hint to get things rolling

A more detailed explanation

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :