Anagram

Time: O(n)

Space: O(1)

Intuition

Two strings are anagrams if they have the same character frequencies. Use a single int[256] array: increment for each character in s1, decrement for each in s2. If all entries are 0, they are anagrams.

Algorithm

1If lengths differ, return false.
2int[256] count. For each i: count[s1[i]]++; count[s2[i]]--.
3Return count.All(x => x == 0).

Example Walkthrough

Input: s1 = "listen", s2 = "silent"

1.After processing: all counts are 0. Return true.

Output: YES

Common Pitfalls

•Use a char frequency array, not sort â€” sort is O(n log n) vs O(n).

Anagram.java

Java

// Approach: Count character frequencies of both strings using a frequency array of size 26.
// If all counts match, they are anagrams.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    // Function is to check whether two strings are anagram of each other or not.
    public static boolean areAnagrams(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        } else {
            HashMap<Character, Integer> h1 = new HashMap<>();
            HashMap<Character, Integer> h2 = new HashMap<>();
            for (int i = 0; i < s1.length(); i++) {
                if (h1.containsKey(s1.charAt(i)))
                    h1.put(s1.charAt(i), h1.get(s1.charAt(i)) + 1);
                else
                    h1.put(s1.charAt(i), 1);
            }
            for (int i = 0; i < s2.length(); i++) {
                if (h2.containsKey(s2.charAt(i)))
                    h2.put(s2.charAt(i), h2.get(s2.charAt(i)) + 1);
                else
                    h2.put(s2.charAt(i), 1);
            }

            return h1.equals(h2);
        }
    }
}

Was this solution helpful?