Anagram Check Techniques in DSA C++ - Execution Trace

Concept Flow - Anagram Check Techniques

Start with two strings

↓

Check length equal?

No→Not anagrams

Yes↓

Choose technique

↓

Sort both

↓

Compare results

No↓

Not anagrams

Start by checking if strings have equal length. Then use sorting, counting, or hash map to compare characters and decide if they are anagrams.

Execution Sample

DSA C++

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

This code checks if two strings are anagrams by sorting and comparing them.

Execution Table

Step	Operation	String 1 State	String 2 State	Comparison Result	Visual State
1	Check length	listen (6 chars)	silent (6 chars)	Equal length	listen | silent
2	Sort s1	eilnst	silent	N/A	eilnst | silent
3	Sort s2	eilnst	eilnst	N/A	eilnst | eilnst
4	Compare sorted	eilnst	eilnst	Equal	eilnst == eilnst
5	Return result	N/A	N/A	True (Anagrams)	Anagrams confirmed
6	Exit	N/A	N/A	End	Process complete

💡 Strings are equal length and sorted forms match, so they are anagrams.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
s1	listen	listen	eilnst	eilnst	eilnst
s2	silent	silent	silent	eilnst	eilnst
length check	N/A	6 == 6 (true)	N/A	N/A	N/A
comparison	N/A	N/A	N/A	eilnst == eilnst (true)	true

Key Moments - 3 Insights

Why do we check string lengths first?

Because if lengths differ (see Step 1 in execution_table), they cannot be anagrams, so we stop early.

Why sorting both strings helps check anagrams?

Sorting arranges characters in order, so equal sorted strings mean same characters with same counts (see Steps 2-4).

Can we use counting characters instead of sorting?

Yes, counting frequency of each character and comparing counts also confirms anagrams without sorting.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of s1 after Step 2?

A listen

B eilnst

C silent

D eilnst (sorted s2)

💡 Hint

Check the 'String 1 State' column at Step 2 in execution_table.

At which step do we confirm the strings are anagrams?

A Step 1

B Step 3

C Step 4

D Step 6

💡 Hint

Look at 'Comparison Result' column where sorted strings are compared.

If the strings had different lengths, what would happen in the execution_table?

A We would proceed to sort both strings

B We would return false immediately after Step 1

C We would compare sorted strings anyway

D We would skip length check

💡 Hint

Refer to Step 1 where length check decides if process continues.

Concept Snapshot

Anagram Check Techniques:
- First check if strings have equal length.
- Sort both strings and compare sorted results.
- Alternatively, count character frequencies and compare.
- If equal, strings are anagrams; else not.
- Sorting method is simple and effective for small strings.

Full Transcript

To check if two strings are anagrams, first verify they have the same length. If not, they cannot be anagrams. Then, either sort both strings and compare if they are equal, or count the frequency of each character in both strings and compare counts. If the sorted strings or counts match, the strings are anagrams. This method ensures all characters and their counts are the same in both strings.

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