Valid Anagram

In this approach, we will use a temporary array to store each character count from input string s and compare character count against input string t or the other way around.

• We will create a function usingArray that takes input arguments string s and t.
• Base case is, if input strings s and t lengths are not same, then we can simply return false because these strings won't be anagrams of each other.
• Create a temporary array with size as 26 if the characters going to be lowercase or uppercase english alphabet letters. (If the characters are going to be ASCII characters, then you can initialize array with 128 size)
• Then, for each character in input string t add character count in correponding position.
Java

int[] arr = new int[26];
for(int i=0; i<s.length(); i++) {
    arr[s.charAt(i) - 'a']++;
}

• Then, for each character in input string s, decrement the count from temporary array that we have created above.
  • If the count at character position becomes -1, this means that the string is not an anagram.
  • If the count at character position never becomes -1, then both strings are anagrams of each other.

public class ValidAnagram {

    /* Using a temporary array */
    static boolean usingArray(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }

        int[] arr = new int[26];
        for(int i=0; i<s.length(); i++) {
            arr[s.charAt(i) - 'a']++;
        }

        for(int j=0; j<t.length(); j++) {
            int charIndex = t.charAt(j) - 'a';
            arr[charIndex] = arr[charIndex] - 1;
            if(arr[charIndex] == -1) {
                return false;
            }
        }
        return true;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(1) since we are creating a temporary array with size 26 or 128 depends on characters type.

In this approach, we will use a HashMap to store each character count from input strings s and t and we store the count of characters of each string into a separate HashMap. Then, for each key in one HashMap check if the character count in other HashMap and see if they are same, if they are same then the strings are anagrams of each other, otherwise they are not anagrams.

import java.util.HashMap;
import java.util.Map.Entry;

public class ValidAnagram {

    /* Using two hashmaps two keep character count of each string s and t */
    static boolean usingTwoHashMap(String s, String t) {
        if(s.length() != t.length()) { // if the lengths are not same, they can't be anagrams
            return false;
        }

        HashMap<Character, Integer> s_count = new HashMap<>();
        HashMap<Character, Integer> t_count = new HashMap<>();
        for(int i=0; i<s.length(); i++) {
            s_count.merge(s.charAt(i), 1, Integer::sum);
            t_count.merge(t.charAt(i), 1, Integer::sum);
        }

        //now, for every character count in s_count, check if the count in t_count matches or not

        for(Entry<Character, Integer> charToCountEntry : s_count.entrySet()) {
            if(!charToCountEntry.getValue().equals(t_count.get(charToCountEntry.getKey()))) {
                return false;
            }
        }
        return true;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(n) since we are storing character count into a HashMap.

This approach is same as solution 1, instead of using an array we will be using a HashMap, so that the solution will work for any type of characters that are in input strings like ASCII or Unicode etc.

import java.util.HashMap;

public class ValidAnagram {

        /* Using a single HashMap - equivalent to using arrays approach*/
    static boolean usingSingleHashMap(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }

        HashMap<Character, Integer> s_count = new HashMap<>();
        for(int i=0; i<s.length(); i++) {
            s_count.merge(s.charAt(i), 1, Integer::sum);
        }

        for(int j=0; j<t.length(); j++) {
            int newValAfter = s_count.merge(t.charAt(j), -1, Integer::sum); // this returns the new value after decrementing the count
            if(newValAfter == -1) {
                return false;
            }
        }
        return true;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string length.
Space complexity: O(n) since we are storing character count into a HashMap.