Anagram Check Techniques in DSA C#

Mental Model

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

Analogy: Imagine two bags of colored beads. If both bags have the exact same colors and number of beads, just arranged differently, they are anagrams.

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

Both have letters c, a, t but in different order.

Dry Run Walkthrough

Input: Check if "listen" and "silent" are anagrams

Goal: Determine if both words have the same letters with the same counts

Step 1: Convert both words to lowercase to ignore case differences

listen, silent

Why: To treat uppercase and lowercase letters as the same

Step 2: Count letters in "listen": l=1, i=1, s=1, t=1, e=1, n=1

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

Why: We need to know how many times each letter appears

Step 3: Count letters in "silent": s=1, i=1, l=1, e=1, n=1, t=1

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

Why: Compare counts to see if they match

Step 4: Compare both counts letter by letter

All counts match

Why: Matching counts means words are anagrams

Result:

listen -> silent: anagrams (same letter counts)

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class AnagramChecker
{
    public static bool AreAnagrams(string s1, string s2)
    {
        if (s1.Length != s2.Length) return false; // quick length check

        var count = new Dictionary<char, int>();

        foreach (char c in s1.ToLower())
        {
            if (count.ContainsKey(c))
                count[c]++;
            else
                count[c] = 1;
        }

        foreach (char c in s2.ToLower())
        {
            if (!count.ContainsKey(c))
                return false; // letter not found in first word
            count[c]--;
            if (count[c] < 0)
                return false; // more occurrences in second word
        }

        return true; // all counts matched
    }

    static void Main()
    {
        string word1 = "listen";
        string word2 = "silent";

        bool result = AreAnagrams(word1, word2);
        Console.WriteLine(result ? "Anagrams" : "Not Anagrams");
    }
}

if (s1.Length != s2.Length) return false; // quick length check

If lengths differ, they cannot be anagrams

foreach (char c in s1.ToLower())

Count each letter in first word ignoring case

if (count.ContainsKey(c)) count[c]++; else count[c] = 1;

Increment count for each letter

foreach (char c in s2.ToLower())

Check letters in second word against counts

if (!count.ContainsKey(c)) return false;

If letter not in first word, not an anagram

count[c]--; if (count[c] < 0) return false;

If second word has more of a letter, not an anagram

return true;

All letters matched in count, words are anagrams

Output

Anagrams

Complexity Analysis

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

Space: O(1) because the dictionary stores counts for at most 26 letters (English alphabet)

vs Alternative: Sorting both words and comparing is O(n log n), so counting letters is faster

Edge Cases

Empty strings

Returns true because empty strings trivially have same letters

DSA C#

if (s1.Length != s2.Length) return false;

Different lengths

Returns false immediately due to length check

DSA C#

if (s1.Length != s2.Length) return false;

Words with uppercase letters

Case is ignored by converting to lowercase

DSA C#

foreach (char c in s1.ToLower())

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: Comparing sorted strings without handling case differences
Fix: Convert both strings to lowercase before sorting or counting

Mistake: Not checking if lengths are equal before counting
Fix: Add a length check to quickly return false if lengths differ

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 does it mean if two strings are anagrams of each other?

easy

A. They have the same characters in the same frequency but possibly different order

B. They have the same length but different characters

C. They start with the same letter

D. They contain only vowels

Solution

1. Step 1: Understand the definition of anagrams

   Anagrams are words or phrases made by rearranging the letters of another, so they must have the same characters with the same counts.

2. Step 2: Compare the options

   Only They have the same characters in the same frequency but possibly different order correctly describes this property; others describe unrelated conditions.

3. Final Answer:

   They have the same characters in the same frequency but possibly different order -> Option A

4. Quick Check:

   Anagram = Same chars & frequency [OK]

Hint: Anagrams have same letters and counts, order doesn't matter [OK]

Common Mistakes:

• Thinking same length means anagram
• Assuming order must be identical
• Confusing anagrams with substrings

2. Which of the following C# code snippets correctly checks if two strings are anagrams by sorting?

easy

A. return s1.Contains(s2);

B. return s1 == s2;

C. return s1.Length == s2.Length;

D. return string.Concat(s1.OrderBy(c => c)) == string.Concat(s2.OrderBy(c => c));

Solution

1. Step 1: Understand sorting approach for anagrams

   Sorting both strings and comparing them checks if they have the same characters in the same order after sorting.

2. Step 2: Analyze each code snippet

   return string.Concat(s1.OrderBy(c => c)) == string.Concat(s2.OrderBy(c => c)); sorts both strings and compares; this is correct. Options B, C, and D do not check anagram conditions properly.

3. Final Answer:

   return string.Concat(s1.OrderBy(c => c)) == string.Concat(s2.OrderBy(c => c)); -> Option D

4. Quick Check:

   Sort & compare strings = correct anagram check [OK]

Hint: Sort both strings and compare to check anagrams [OK]

Common Mistakes:

• Comparing strings directly without sorting
• Only checking length equality
• Using Contains instead of full comparison

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

string s1 = "listen";
string s2 = "silent";
bool result = s1.OrderBy(c => c).SequenceEqual(s2.OrderBy(c => c));
Console.WriteLine(result);

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Sort both strings and compare sequences

   The code sorts characters of both strings and checks if sequences are equal. "listen" and "silent" are anagrams.

2. Step 2: Evaluate the result of SequenceEqual

   Since sorted characters match, SequenceEqual returns true, so Console.WriteLine prints True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Sorted anagrams equal = True [OK]

Hint: Sorted anagrams produce true when compared with SequenceEqual [OK]

Common Mistakes:

• Assuming order matters before sorting
• Confusing SequenceEqual with Equals
• Expecting false because strings differ initially

4. Identify the bug in this C# method intended to check anagrams:

bool AreAnagrams(string s1, string s2) {
  if (s1.Length != s2.Length) return false;
  var dict = new Dictionary();
  foreach (var c in s1) {
    dict[c] = dict.ContainsKey(c) ? dict[c] + 1 : 1;
  }
  foreach (var c in s2) {
    if (!dict.ContainsKey(c)) return false;
    dict[c]--;
  }
  return true;
}

medium

A. It does not check string lengths

B. It uses a dictionary instead of array

C. It does not check if counts go below zero

D. It returns false too early

Solution

1. Step 1: Review dictionary count decrement logic

   The method decrements counts for characters in s2 but never checks if count becomes negative, which means extra characters in s2 are not detected.

2. Step 2: Identify missing validation

   Without checking if dict[c] < 0 after decrement, method can wrongly return true when s2 has extra characters.

3. Final Answer:

   It does not check if counts go below zero -> Option C

4. Quick Check:

   Check negative counts after decrement to fix bug [OK]

Hint: Always verify counts don't go negative when decrementing [OK]

Common Mistakes:

• Ignoring negative counts after decrement
• Assuming length check is enough
• Not using dictionary for frequency

5. You want to check if two strings are anagrams ignoring case and spaces. Which approach is best in C#?

hard

A. Count characters without removing spaces

B. Remove spaces, convert to lowercase, then sort and compare

C. Compare strings directly ignoring case

D. Check if lengths are equal ignoring spaces

Solution

1. Step 1: Normalize strings by removing spaces and converting to lowercase

   This ensures spaces and case differences do not affect comparison.

2. Step 2: Sort normalized strings and compare

   Sorting both normalized strings and comparing confirms if they are anagrams ignoring case and spaces.

3. Final Answer:

   Remove spaces, convert to lowercase, then sort and compare -> Option B

4. Quick Check:

   Normalize then sort & compare for case/space insensitive anagram [OK]

Hint: Normalize strings by removing spaces and lowercasing before checking [OK]

Common Mistakes:

• Not removing spaces before comparison
• Ignoring case differences
• Only checking length equality