Valid Anagram

12 May 2026 0 Likes

Problem Description

Given two strings s and t, return true if t is an anagram of s, and return false otherwise.

An anagram is formed when two strings contain the same characters with the same frequency, but the arrangement of characters may be different.
Example 1:
Input: s = "anagram", t = "nagaram"
 Output: true
Explanation: Both strings contain the same characters with identical frequencies.
Example 2:
Input: s = "rat", t = "car"
 Output: false
Explanation: The characters in both strings are different, so they are not anagrams.
Example 3:
Input: s = "listen", t = "silent"
 Output: true
Explanation: Both strings contain the same characters arranged in different order.

Constraints

Both strings contain only lowercase English letters. The length of each string may range from small to large input sizes depending on platform limits.

The output should be:

true → if both strings are anagrams
false → otherwise

An efficient solution is expected to minimize unnecessary repeated character comparisons.

Understanding the Problem

The problem is asking us to determine whether two strings contain exactly the same characters with the same frequencies.

A simple way to understand the problem is by using a brute-force approach. We can compare the frequency of every character present in the first string with its frequency in the second string.

For example, if: s = "anagram" and t = "nagaram"

Then the character counts become:

a → 3 times
n → 1 time
g → 1 time
r → 1 time
m → 1 time

Since both strings contain identical character frequencies, they are considered valid anagrams. If even one character appears a different number of times, the strings cannot be anagrams.

This frequency comparison approach helps clearly understand the actual requirement of the problem.

Hints

The first hint is to observe that two strings cannot be anagrams if their lengths are different.

Another important observation is that anagrams always contain the same characters with identical frequencies.

Instead of repeatedly counting characters manually, try storing character frequencies using a HashMap or frequency array.

If the frequency of every character matches in both strings, the strings are valid anagrams.

Solutions

BETTER

HashMap Frequency Counting Solution

This approach uses a HashMap to store the frequency of characters present in the first string.

First, we check whether both strings have the same length. If their lengths are different, they cannot be valid anagrams.

Next, we traverse the first string and store the frequency of every character inside the map.

Then we traverse the second string and decrease the frequency count for each character.

If a character does not exist in the map or its frequency becomes negative, it means the strings contain different character frequencies, so we return false.

If all frequencies are balanced successfully, both strings are valid anagrams.

This approach avoids sorting and provides better performance using efficient hash-based lookup operations.
public class B_Map {

    public boolean isAnagram(String s, String t) {

        if (s.length() != t.length())
            return false;

        Map<Character, Integer> charCount = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {

            charCount.put(
                    s.charAt(i),
                    charCount.getOrDefault(s.charAt(i), 0) + 1
            );
        }

        for (int i = 0; i < t.length(); i++) {

            if (!charCount.containsKey(t.charAt(i)))
                return false;

            charCount.put(
                    t.charAt(i),
                    charCount.get(t.charAt(i)) - 1
            );

            if (charCount.get(t.charAt(i)) < 0)
                return false;

        }

        return true;
    }
}
class Solution:

    def isAnagram(self, s, t):

        if len(s) != len(t):
            return False

        char_count = {}

        for ch in s:
            char_count[ch] = char_count.get(ch, 0) + 1

        for ch in t:

            if ch not in char_count:
                return False

            char_count[ch] -= 1

            if char_count[ch] < 0:
                return False

        return True
Time Complexity
O(n)
Space Complexity
O(n)
BRUTE FORCE

Sorting Based Anagram Checking Solution

This approach converts both strings into character arrays and sorts them individually.

If two strings are valid anagrams, then after sorting, both strings will become exactly identical because the same characters will appear in the same order.

For example:

"anagram" becomes "aaagmnr"
"nagaram" also becomes "aaagmnr"

Since both sorted strings are equal, the strings are valid anagrams.

If the sorted results are different, then the strings cannot be anagrams.

This approach is simple and easy to understand, but sorting introduces additional overhead.
public class A_BruteForce {

    public boolean isAnagram(String s, String t) {

        char[] sa = s.toCharArray();
        char[] st = t.toCharArray();

        Arrays.sort(sa);
        Arrays.sort(st);

        s = new String(sa);
        t = new String(st);

        return s.equals(t);
    }
}
class Solution:

    def isAnagram(self, s, t):

        s_sorted = sorted(s)
        t_sorted = sorted(t)

        return s_sorted == t_sorted
Time Complexity
O(n log n)
Space Complexity
O(n)
OPTIMAL

Optimal Character Frequency Array Solution

This approach uses a fixed-size character frequency array to efficiently track the count of lowercase English letters.

Since the problem contains only lowercase English characters, we can use an integer array of size 26, where each index represents a character from 'a' to 'z'.

First, we check whether both strings have equal lengths. If the lengths differ, the strings cannot be anagrams.

Then, during a single traversal:

We increase the frequency count for characters from the first string and decrease the frequency count for characters from the second string.

After processing both strings, every frequency value should become 0 if both strings contain identical character counts.

If any frequency remains non-zero, the strings are not valid anagrams.

This solution is highly efficient because it avoids sorting and uses only constant extra space.
class Solution:

    def isAnagram(self, s, t):

        if len(s) != len(t):
            return False

        char_count = [0] * 26

        for i in range(len(s)):

            char_count[ord(s[i]) - ord('a')] += 1
            char_count[ord(t[i]) - ord('a')] -= 1

        for count in char_count:

            if count != 0:
                return False

        return True
public class C_CharArray {

    public boolean isAnagram(String s, String t) {

        if (s.length() != t.length())
            return false;

        int[] charCount = new int[26];

        for (int i = 0; i < s.length(); i++) {

            charCount[s.charAt(i) - 'a']++;

            charCount[t.charAt(i) - 'a']--;
        }

        for (int i : charCount) {

            if (i != 0)
                return false;

        }

        return true;
    }
}
Time Complexity
O(n)
Space Complexity
O(1)

Conclusion

The Valid Anagram problem is an important beginner-level string problem that teaches frequency counting and efficient character tracking techniques.

Although direct comparison approaches help in understanding the problem, optimized solutions using sorting or hashing provide significantly better performance and cleaner implementation.

Mastering this problem helps build a strong foundation for solving advanced problems involving strings, character frequency analysis, and hash-based data structures.

💬 Comments