Valid Anagram

🎯

Valid Anagram

easyHASH_MAPAmazonFacebookMicrosoft

Imagine you want to quickly check if two words are just jumbled versions of each other, like 'listen' and 'silent'. This problem helps you verify that efficiently.

💡 This problem is about comparing character frequencies between two strings. Beginners often struggle because they try to compare strings directly without counting characters, missing the core insight that anagrams have identical character counts.

📋

Problem Statement

Given two strings s and t, write a function to determine if t is an anagram of s. Return true if t is an anagram of s, and false otherwise. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, using all the original letters exactly once.

1 ≤ length of s, t ≤ 10^5s and t consist of lowercase English letters only

💡

Example

Input"s = 'anagram', t = 'nagaram'"

Outputtrue

Both strings have the same characters with the same frequency.

Input"s = 'rat', t = 'car'"

Outputfalse

Characters differ; 'car' has 'c' which 'rat' does not.

• Empty strings s = '', t = '' → true
• Strings of different lengths s = 'a', t = 'aa' → false
• Strings with same letters but different counts s = 'aabb', t = 'abab' → true
• Strings with unicode or uppercase letters (not allowed by constraints) → should handle only lowercase

⚠️

Common Mistakes

Not checking string lengths before processing

Unnecessary computation or incorrect results when strings differ in length

✅ Add an early length check and return false if lengths differ

Using hash map but forgetting to decrement counts for second string

Incorrectly returns true even if strings differ in character counts

✅ Decrement counts for characters in the second string and check for negatives

Assuming sorted strings are always equal without length check

May cause index errors or false positives

✅ Always check lengths before sorting and comparing

Using fixed array without handling characters outside 'a'-'z'

Index out of range errors or incorrect results

✅ Confirm input constraints or use hash map for general characters

Not testing empty strings or single-character strings

May miss edge cases leading to wrong answers

✅ Include edge cases in tests and handle empty inputs gracefully

🧠

Brute Force (Sorting Both Strings)

💡 Sorting both strings is a straightforward way to compare character order and frequency. It’s easy to implement and understand, making it a great starting point.

Intuition

If two strings are anagrams, sorting their characters will produce identical strings. So, sorting both and comparing is a direct check.

Algorithm

1. Check if lengths of s and t are equal; if not, return false immediately.
2. Convert both strings to character arrays and sort them.
3. Compare the sorted arrays character by character.
4. Return true if all characters match; otherwise, false.

💡 Sorting makes the problem easier to visualize but costs extra time; beginners often overlook the length check which can save time.

</>

Code

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

# Driver code
if __name__ == '__main__':
    print(isAnagram('anagram', 'nagaram'))  # True
    print(isAnagram('rat', 'car'))          # False

Line Notes

def isAnagram(s: str, t: str) -> bool:Function signature with type hints for clarity

if len(s) != len(t):Quickly eliminate strings of different lengths to save unnecessary work

return sorted(s) == sorted(t)Sorting both strings and comparing is the core brute force check

print(isAnagram('anagram', 'nagaram'))Example test to verify correctness

import java.util.Arrays;

public class ValidAnagram {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        return Arrays.equals(sArr, tArr);
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram")); // true
        System.out.println(isAnagram("rat", "car"));         // false
    }
}

Line Notes

if (s.length() != t.length()) return false;Early exit if lengths differ to optimize

char[] sArr = s.toCharArray();Convert string to char array for sorting

Arrays.sort(sArr);Sort characters to compare order and frequency

return Arrays.equals(sArr, tArr);Check if sorted arrays are identical

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    return s == t;
}

int main() {
    cout << boolalpha << isAnagram("anagram", "nagaram") << endl; // true
    cout << boolalpha << isAnagram("rat", "car") << endl;         // false
    return 0;
}

Line Notes

if (s.length() != t.length()) return false;Avoid unnecessary sorting if lengths differ

sort(s.begin(), s.end());Sort string s in-place to compare characters

return s == t;Direct string comparison after sorting

cout << boolalpha << isAnagram(...)Print boolean results as true/false for clarity

function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    return s.split('').sort().join('') === t.split('').sort().join('');
}

// Test cases
console.log(isAnagram('anagram', 'nagaram')); // true
console.log(isAnagram('rat', 'car'));         // false

Line Notes

if (s.length !== t.length) return false;Quick length check to avoid extra work

s.split('').sort().join('')Sort characters of string s for comparison

return ... === ...Compare sorted strings directly

console.log(isAnagram('anagram', 'nagaram'));Test output to verify correctness

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n) time and requires O(n) space for the sorted arrays or strings.

💡 For n=100,000 characters, sorting is efficient but not the fastest possible; it means about 1.5 million operations roughly.

Interview Verdict: Accepted

This approach passes all tests but is not optimal; it’s a good baseline to understand before optimizing.

🧠

Frequency Counting Using Hash Map

💡 Counting character frequencies directly is more efficient than sorting. It leverages hash maps to track counts, which is a common pattern in string problems.

Intuition

If two strings have the same frequency of each character, they are anagrams. Counting frequencies and comparing is a direct way to verify this.

Algorithm

1. If lengths differ, return false immediately.
2. Create a hash map to count characters in s.
3. Iterate over t, decrementing counts in the hash map.
4. If any count goes below zero or a character is missing, return false.
5. If all counts are zero at the end, return true.

💡 This approach requires careful handling of increments and decrements to avoid off-by-one errors.

</>

Code

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for ch in t:
        if ch not in count or count[ch] == 0:
            return False
        count[ch] -= 1
    return True

# Driver code
if __name__ == '__main__':
    print(isAnagram('anagram', 'nagaram'))  # True
    print(isAnagram('rat', 'car'))          # False

Line Notes

if len(s) != len(t):Early exit to avoid unnecessary counting

count = {}Initialize dictionary to store character counts

count[ch] = count.get(ch, 0) + 1Increment count for each character in s

if ch not in count or count[ch] == 0:Check if t has extra or missing characters

import java.util.HashMap;

public class ValidAnagram {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        HashMap<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) {
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        for (char c : t.toCharArray()) {
            if (!count.containsKey(c) || count.get(c) == 0) return false;
            count.put(c, count.get(c) - 1);
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram")); // true
        System.out.println(isAnagram("rat", "car"));         // false
    }
}

Line Notes

if (s.length() != t.length()) return false;Length check to optimize early

HashMap<Character, Integer> count = new HashMap<>();Create map to track character frequencies

count.put(c, count.getOrDefault(c, 0) + 1);Increment count for each character in s

if (!count.containsKey(c) || count.get(c) == 0) return false;Detect extra or missing characters in t

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    unordered_map<char, int> count;
    for (char c : s) count[c]++;
    for (char c : t) {
        if (count.find(c) == count.end() || count[c] == 0) return false;
        count[c]--;
    }
    return true;
}

int main() {
    cout << boolalpha << isAnagram("anagram", "nagaram") << endl; // true
    cout << boolalpha << isAnagram("rat", "car") << endl;         // false
    return 0;
}

Line Notes

if (s.length() != t.length()) return false;Avoid unnecessary processing if lengths differ

unordered_map<char, int> count;Hash map to store character counts

for (char c : s) count[c]++;Count characters in s

if (count.find(c) == count.end() || count[c] == 0) return false;Check for invalid or extra characters in t

function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    const count = {};
    for (const ch of s) {
        count[ch] = (count[ch] || 0) + 1;
    }
    for (const ch of t) {
        if (!count[ch]) return false;
        count[ch]--;
    }
    return true;
}

// Test cases
console.log(isAnagram('anagram', 'nagaram')); // true
console.log(isAnagram('rat', 'car'));         // false

Line Notes

if (s.length !== t.length) return false;Quick length check to optimize

const count = {};Object used as hash map for counts

count[ch] = (count[ch] || 0) + 1;Increment count for each character in s

if (!count[ch]) return false;Detect if t has extra characters or count exhausted

⏱

Complexity

TimeO(n)

SpaceO(1)

Counting characters takes O(n) time. Space is O(1) because the character set is fixed (26 lowercase letters).

💡 For n=100,000, this means about 100,000 operations, which is very efficient compared to sorting.

Interview Verdict: Accepted

This approach is optimal for this problem and is preferred in interviews.

🧠

Frequency Counting Using Fixed-Size Array

💡 Since the problem states only lowercase English letters, we can use a fixed-size array of length 26 instead of a hash map for even faster access and less overhead.

Intuition

Map each character to an index in an array and count frequencies. This avoids hash map overhead and uses constant space.

Algorithm

1. If lengths differ, return false immediately.
2. Create an integer array of size 26 initialized to zero.
3. Increment counts for characters in s by mapping 'a' to 0, 'b' to 1, etc.
4. Decrement counts for characters in t similarly.
5. If any count is not zero at the end, return false; otherwise, true.

💡 This approach requires careful indexing but is very efficient and uses minimal memory.

</>

Code

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    count = [0] * 26
    for ch in s:
        count[ord(ch) - ord('a')] += 1
    for ch in t:
        count[ord(ch) - ord('a')] -= 1
        if count[ord(ch) - ord('a')] < 0:
            return False
    return True

# Driver code
if __name__ == '__main__':
    print(isAnagram('anagram', 'nagaram'))  # True
    print(isAnagram('rat', 'car'))          # False

Line Notes

count = [0] * 26Initialize fixed-size array for 26 letters

count[ord(ch) - ord('a')] += 1Map character to index and increment count

count[ord(ch) - ord('a')] -= 1Decrement count for characters in t

if count[ord(ch) - ord('a')] < 0:Detect if t has extra characters

public class ValidAnagram {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram")); // true
        System.out.println(isAnagram("rat", "car"));         // false
    }
}

Line Notes

int[] count = new int[26];Fixed array for character counts

count[s.charAt(i) - 'a']++;Increment count for s's character

count[t.charAt(i) - 'a']--;Decrement count for t's character in same loop

for (int c : count) { if (c != 0) return false; }Check if all counts balanced

#include <iostream>
#include <string>

using namespace std;

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    int count[26] = {0};
    for (int i = 0; i < s.length(); i++) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) return false;
    }
    return true;
}

int main() {
    cout << boolalpha << isAnagram("anagram", "nagaram") << endl; // true
    cout << boolalpha << isAnagram("rat", "car") << endl;         // false
    return 0;
}

Line Notes

int count[26] = {0};Initialize fixed-size array for counts

count[s[i] - 'a']++;Increment count for s's character

count[t[i] - 'a']--;Decrement count for t's character in same iteration

if (count[i] != 0) return false;Verify all counts are zero at the end

function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    const count = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i) - 97]++;
        count[t.charCodeAt(i) - 97]--;
    }
    for (const c of count) {
        if (c !== 0) return false;
    }
    return true;
}

// Test cases
console.log(isAnagram('anagram', 'nagaram')); // true
console.log(isAnagram('rat', 'car'));         // false

Line Notes

const count = new Array(26).fill(0);Create fixed-size array for counts

count[s.charCodeAt(i) - 97]++;Increment count for s's character

count[t.charCodeAt(i) - 97]--;Decrement count for t's character

if (c !== 0) return false;Check if counts are balanced at the end

⏱

Complexity

TimeO(n)

SpaceO(1)

Counting with a fixed array is O(n) time and uses constant space since array size is fixed at 26.

💡 This is the fastest and most memory-efficient approach for this problem.

Interview Verdict: Accepted

This is the optimal approach to implement in interviews when constraints allow.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the fixed array frequency counting approach is best to code due to its optimal time and space. Sorting is easiest to explain but slower.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Sorting Both Strings)	O(n log n)	O(n)	No	N/A	Mention only - never code unless asked for simple solution
2. Frequency Counting Using Hash Map	O(n)	O(1) (constant for fixed charset)	No	N/A	Good approach if character set unknown or large
3. Frequency Counting Using Fixed-Size Array	O(n)	O(1)	No	N/A	Best approach for lowercase English letters; code this in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and finally optimize step-by-step.

How to Present

Step 1: Clarify the problem and constraints, especially character set and string lengths.Step 2: Present the brute force approach using sorting and explain its time complexity.Step 3: Introduce the hash map frequency counting approach for better efficiency.Step 4: Optimize further using a fixed-size array if the character set is limited.Step 5: Write clean, tested code and discuss edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your ability to identify the right data structure (hash map or array), optimize time and space, and handle edge cases correctly.

Common Follow-ups

• What if the strings contain Unicode characters? → Use a hash map instead of fixed array.
• How to handle case-insensitive anagrams? → Convert both strings to lowercase before processing.

💡 These follow-ups test your adaptability to variations in input and constraints.

🔍

Pattern Recognition

When to Use

1) Need to compare two strings for rearranged characters; 2) Problem mentions anagrams or permutations; 3) Character frequency matters; 4) Constraints allow counting characters efficiently.

Signature Phrases

anagramrearranged letterssame charactersfrequency count

NOT This Pattern When

Problems that require substring matching without rearrangement or problems focusing on subsequences rather than permutations.

Similar Problems

Group Anagrams - grouping strings by character frequencyMinimum Window Substring - tracking character counts in a sliding window

Practice

1. You are given a string and need to find the index of the first character that appears exactly once. Which approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Use a greedy approach that picks the first character that is not equal to its adjacent characters.

B. Use a brute force nested loop to compare each character with every other character.

C. Use a dynamic programming approach to store subproblems of unique characters.

D. Use a single pass to track each character's frequency and first occurrence index, then find the minimum index with frequency one.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the first unique character's index efficiently.

2. Step 2: Identify approach that tracks frequency and first occurrence in one pass

   Only the single pass with frequency and index tracking guarantees O(n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass frequency + index tracking is optimal [OK]

Hint: Track frequency and first index in one pass [OK]

Common Mistakes:

• Assuming greedy adjacent check works
• Using DP unnecessarily
• Brute force is optimal

2. You are given two strings s and t. You need to determine if there exists a one-to-one character mapping from s to t such that replacing characters in s with their mapped characters produces t. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming to track substring isomorphisms

B. Greedy approach that maps characters as they appear without checking reverse mapping

C. Bidirectional hash map mapping that ensures one-to-one character correspondence

D. Brute force nested loops checking all character pairs for consistency

Solution

1. Step 1: Understand the problem constraints

   The problem requires a one-to-one mapping between characters of two strings, ensuring no two characters in s map to the same character in t and vice versa.

2. Step 2: Identify the approach that enforces bidirectional mapping

   Only the bidirectional hash map approach maintains two maps: one from s to t and another from t to s, ensuring the mapping is consistent and one-to-one.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional mapping prevents false positives like mapping "ab" to "aa" [OK]

Hint: One-to-one mapping requires bidirectional checks [OK]

Common Mistakes:

• Assuming single-direction mapping suffices
• Using DP which is unnecessary
• Relying on greedy without reverse check

3. You are given an integer array and need to find the k elements that appear most frequently. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Use a frequency map and bucket sort to group elements by their frequency, then collect top k from highest frequency buckets.

B. Sort the entire array and pick the top k elements by frequency.

C. Use a greedy approach that picks elements as they appear until k elements are chosen.

D. Use dynamic programming to build frequency counts and select top k elements.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding top k frequent elements efficiently, ideally in linear time.

2. Step 2: Identify approach with linear time complexity

   Bucket sort groups elements by frequency, allowing O(n) time retrieval of top k elements by scanning buckets from high to low frequency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort approach is known to run in O(n) time for this problem [OK]

Hint: Bucket sort groups by frequency for O(n) retrieval [OK]

Common Mistakes:

• Sorting entire array is O(n log n), not optimal
• Greedy approach ignores frequency counts
• DP is unrelated to frequency counting here

4. Identify the bug in the following Python code for detecting duplicates:

medium

A. Line 2: initializing the set should be a list

B. Line 6: returning False outside the loop is incorrect

C. Line 4: adding the number before checking membership causes always True

D. Line 5: the membership check should use 'not in' instead of 'in'

Solution

1. Step 1: Analyze the order of operations

   The code adds the number to the set before checking if it is already present, so the membership check always returns True on the first iteration.

2. Step 2: Identify the bug

   Membership check must occur before adding the number to avoid false positives.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding before checking membership causes immediate True return [OK]

Hint: Check membership before adding to avoid false positives [OK]

Common Mistakes:

• Adding before checking membership
• Misplacing return statements
• Confusing set initialization

5. The following code attempts to detect a continuous subarray sum divisible by k. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: normalizing k if negative

B. Line 9: computing total modulo k without handling negative values

C. Line 3: initializing remainder_map with {0: -1}

D. Line 12: checking if subarray length > 1

Solution

1. Step 1: Identify modulo operation on line 9

   The code uses total = total % k without adjusting for negative totals, which can yield negative remainders.

2. Step 2: Understand impact of negative remainders

   Negative remainders cause incorrect remainder_map keys, missing valid subarrays.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Modulo must be normalized to non-negative remainder [OK]

Hint: Modulo with negatives must be normalized to positive remainder [OK]

Common Mistakes:

• Not normalizing modulo results for negative sums
• Overwriting remainder_map entries instead of preserving earliest index
• Allowing subarrays of length 1 to return True