Anagram Check Techniques in DSA C++

Mental Model

Two words are anagrams if they have the exact same letters in the same amounts, just mixed differently.

Analogy: Imagine two bags of colored beads. If both bags have the same number of beads of each color, they are anagrams, even if the beads are arranged differently inside.

word1: c -> a -> t -> null
word2: t -> a -> c -> null

We want to check if both have the same letters and counts.

Dry Run Walkthrough

Input: word1: "listen", word2: "silent"

Goal: Check if 'listen' and 'silent' are anagrams by comparing letter counts

Step 1: Count letters in 'listen'

{l:1, i:1, s:1, t:1, e:1, n:1}

Why: We need to know how many times each letter appears in the first word

Step 2: Count letters in 'silent'

{s:1, i:1, l:1, e:1, n:1, t:1}

Why: We count letters in the second word to compare with the first

Step 3: Compare both counts

Both have {l:1, i:1, s:1, t:1, e:1, n:1}

Why: If counts match exactly, words are anagrams

Result:

Both words have the same letter counts: anagrams confirmed

Annotated Code

DSA C++

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

bool areAnagrams(const std::string& word1, const std::string& word2) {
    if (word1.length() != word2.length()) return false; // quick length check

    std::unordered_map<char, int> countMap;

    // Count letters in word1
    for (char ch : word1) {
        countMap[ch]++;
    }

    // Subtract counts using word2
    for (char ch : word2) {
        if (countMap.find(ch) == countMap.end() || countMap[ch] == 0) {
            return false; // letter missing or extra in word2
        }
        countMap[ch]--;
    }

    return true; // all counts matched
}

int main() {
    std::string word1 = "listen";
    std::string word2 = "silent";

    if (areAnagrams(word1, word2)) {
        std::cout << word1 << " and " << word2 << " are anagrams\n";
    } else {
        std::cout << word1 << " and " << word2 << " are NOT anagrams\n";
    }

    return 0;
}

if (word1.length() != word2.length()) return false;

quickly reject if lengths differ -- no need to check further

for (char ch : word1) { countMap[ch]++; }

count each letter in the first word

for (char ch : word2) { if (countMap.find(ch) == countMap.end() || countMap[ch] == 0) return false; countMap[ch]--; }

reduce counts for letters in second word; if letter missing or count zero, words differ

return true;

all letters matched perfectly, so words are anagrams

Output

listen and silent are anagrams

Complexity Analysis

Time: O(n) because we count letters in both words once, where n is the length of the words

Space: O(1) because the count map stores at most 26 letters for English alphabet, a fixed size

vs Alternative: Sorting both words takes O(n log n) time, which is slower than counting letters in O(n)

Edge Cases

empty strings

returns true since both are empty and trivially anagrams

DSA C++

if (word1.length() != word2.length()) return false;

different lengths

returns false immediately without counting

DSA C++

if (word1.length() != word2.length()) return false;

same letters different counts (e.g., 'aabb' vs 'ababab')

returns false because counts do not match

DSA C++

if (countMap.find(ch) == countMap.end() || countMap[ch] == 0) return false;

When to Use This Pattern

When you need to check if two strings have the same letters in any order, use letter counting to quickly verify anagrams.

Common Mistakes

Mistake: Only checking if sorted strings are equal without considering performance
Fix: Use counting method for O(n) time instead of sorting for O(n log n)

Mistake: Not checking length first, causing unnecessary work
Fix: Add length check at start to quickly reject impossible cases

Mistake: Not handling letters that appear more times in second word
Fix: Check if count goes below zero when subtracting counts

Summary

Checks if two words have the same letters in the same amounts regardless of order.

Use when you want to verify if two strings are anagrams efficiently.

Counting letters and comparing counts is faster and simpler than sorting.

Practice

1. What is the main idea behind checking if two strings are anagrams?

easy

A. Both strings have the same characters with the same frequency

B. Both strings have the same length only

C. Both strings start with the same character

D. Both strings contain only alphabets

Solution

1. Step 1: Understand what an anagram means

   An anagram means two strings contain the same characters with the same frequency, but possibly in different orders.

2. Step 2: Identify the key condition for anagram check

   The key condition is that both strings must have the same characters appearing the same number of times.

3. Final Answer:

   Both strings have the same characters with the same frequency -> Option A

4. Quick Check:

   Anagram = Same characters & frequency [OK]

Hint: Check character counts match for both strings [OK]

Common Mistakes:

• Only checking string length
• Ignoring character frequency
• Assuming order matters
• Checking only first character

2. Which of the following C++ code snippets correctly sorts a string s to help check an anagram?

easy

A. std::sort(s.begin(), s.end());

B. sort(s, s+length);

C. std::sort(s, s+strlen(s));

D. sort(s.begin(), s.end(), compare);

Solution

1. Step 1: Identify correct sorting syntax for std::string

   For std::string, sorting is done using iterators: s.begin() and s.end().

2. Step 2: Check each option for correctness

   std::sort(s.begin(), s.end()); uses std::sort(s.begin(), s.end()); which is correct. sort(s, s+length); and C use pointer arithmetic which is invalid for std::string. sort(s.begin(), s.end(), compare); uses a comparator but is incomplete without defining it.

3. Final Answer:

   std::sort(s.begin(), s.end()); -> Option A

4. Quick Check:

   Sort string with iterators = std::sort(s.begin(), s.end()) [OK]

Hint: Use s.begin() and s.end() with std::sort for strings [OK]

Common Mistakes:

• Using pointer arithmetic on std::string
• Forgetting std:: namespace
• Using incomplete comparator
• Sorting only part of the string

3. What will be the output of the following C++ code snippet?

std::string s1 = "listen";
std::string s2 = "silent";
std::sort(s1.begin(), s1.end());
std::sort(s2.begin(), s2.end());
if (s1 == s2) std::cout << "Anagrams";
else std::cout << "Not Anagrams";

medium

A. Not Anagrams

B. Anagrams

C. Compilation Error

D. Runtime Error

Solution

1. Step 1: Sort both strings

   After sorting, s1 becomes "eilnst" and s2 becomes "eilnst".

2. Step 2: Compare sorted strings

   Since both sorted strings are equal, the condition s1 == s2 is true, so it prints "Anagrams".

3. Final Answer:

   Anagrams -> Option B

4. Quick Check:

   Sorted strings equal = Anagrams [OK]

Hint: Sort both strings and compare for equality [OK]

Common Mistakes:

• Not sorting strings before comparison
• Confusing output with original strings
• Assuming order matters
• Ignoring case sensitivity

4. Identify the error in the following C++ code for checking anagrams:

bool areAnagrams(std::string s1, std::string s2) {
    if (s1.length() != s2.length()) return false;
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    return s1.compare(s2);
}

medium

A. Length check is incorrect

B. Missing header <algorithm> for sort

C. Strings should be passed by reference

D. Using s1.compare(s2) returns int, not bool

Solution

1. Step 1: Understand std::string::compare return type

   The compare function returns 0 if strings are equal, else non-zero integer.

2. Step 2: Check return type of function

   The function returns bool but returns s1.compare(s2) which is int, so it will not return correct boolean value.

3. Final Answer:

   Using s1.compare(s2) returns int, not bool -> Option D

4. Quick Check:

   compare() returns int, need == 0 for bool [OK]

Hint: Use (s1.compare(s2) == 0) to get bool result [OK]

Common Mistakes:

• Returning compare() directly as bool
• Ignoring header includes
• Passing strings by value unnecessarily
• Incorrect length check logic

5. Given two strings, which approach is best to check anagrams efficiently when strings contain only lowercase English letters?

hard

A. Sort both strings and compare

B. Use nested loops to check each character presence

C. Use a frequency array of size 26 to count characters

D. Convert strings to uppercase and compare

Solution

1. Step 1: Analyze sorting approach

   Sorting takes O(n log n) time, which is good but not optimal for fixed character set.

2. Step 2: Analyze frequency array approach

   Using a frequency array of size 26 counts characters in O(n) time, which is faster and uses constant extra space.

3. Step 3: Compare other options

   Nested loops are inefficient O(n^2). Converting case does not check anagram correctness.

4. Final Answer:

   Use a frequency array of size 26 to count characters -> Option C

5. Quick Check:

   Frequency array = O(n) efficient anagram check [OK]

Hint: Count chars with array for O(n) anagram check [OK]

Common Mistakes:

• Using sorting for large strings unnecessarily
• Using nested loops causing slow performance
• Ignoring character set constraints
• Assuming case conversion solves anagram check