Check if two strings are anagram of each other

A string is said to be an anagram of another string if they satisfy the following conditions

• They consist of same letters in their composition
• The count of each letter is equal in both String

Example

node and done are anagrams of each other.

Approach

Count the occurrence of each character of both the strings and compare them. If we find a difference in count for any character, then its not an anagram.

Algorithm

1. Create a Hashmap named charDiff to store the difference of count for each character in firstString and secondString.
2. Iterate through the firstString:
   1. Check if the character is present in the charDiff:
      1. Present: Increment value of charDiff for that character by 1
      2. Not Present: Make the value of charDiff as 1 for that character
3. Iterate through the secondString:
   1. Check if the character is present in the charDiff:
      1. Present: Decrement value of charDiff for that character by 1
      2. Not Present: Make the value of charDiff as 1 for that character
4. Iterate through the charDiff:
   1. If the value of the current character is not 0:
      1. Return false, as the strings are not anagrams
5. Return true, as the strings are anagrams

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

The Time Complexity of the algorithm is linear as we are just iterating through both the strings and the Space Complexity is also linear because in the worst case all the characters of both the strings will be different and we have to store all of them in the Map.

Java Code

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



class StringAnagram {

    public static Boolean isStringsAnagram(String firstString, String secondString) {

        // A map to store the difference between each character count of firstString and secondString
        Map<Character, Integer> charDiff = new HashMap<Character, Integer>();

        // For each character increment the charDiff of that character
        for (int index = 0; index < firstString.length(); index++) {
            Character currentChar = firstString.charAt(index);

            if (charDiff.containsKey(currentChar)) {
                charDiff.put(currentChar, charDiff.get(currentChar) + 1);
            } else {
                charDiff.put(currentChar, 1);
            }
        }

        // For each character decrement the charDiff of that character
        for (int index = 0; index < secondString.length(); index++) {
            Character currentChar = secondString.charAt(index);

            if (charDiff.containsKey(currentChar)) {
                charDiff.put(currentChar, charDiff.get(currentChar) - 1);
            } else {
                charDiff.put(currentChar, -1);
            }
        }

        // Iterate through every character and check the difference
        for (Map.Entry<Character, Integer> charEntry : charDiff.entrySet()) {
            
            // if the difference is non zero then both the string are not anagrams of each other
            if (charEntry.getValue() != 0) {
                return false;
            }
        }

        // Return true as every character had difference as zero
        return true;

    }

    public static void main(String[] args) {

        String firstString1 = "TeamFunDesk";
        String secondString1 = "TeamBoom";
        if (isStringsAnagram(firstString1, secondString1)) {
            System.out.println("Strings " + firstString1 + " and " + secondString1 + " are anagrams");
        } else {
            System.out.println("Strings " + firstString1 + " and " + secondString1 + " are not " +
                               "anagrams");
        }

        String firstString2 = "night";
        String secondString2 = "thing";
        if (isStringsAnagram(firstString2, secondString2)) {
            System.out.println("Strings " + firstString2 + " and " + secondString2 + " are anagrams of " +
                               "each other");
        } else {
            System.out.println("Strings " + firstString2 + " and " + secondString2 + " are not anagrams" +
                               "of each other");
        }
    }
}

Output

Strings TeamFunDesk and TeamBoom are not anagrams
Strings night and thing are anagrams of each other