Anagram Check Techniques in DSA Rust

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 counts of beads, they are anagrams, even if the beads are arranged differently inside.

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

Check if both have 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 counts match exactly

Why: If counts are the same, words are anagrams.

Result:

"listen" and "silent" are anagrams

Annotated Code

DSA Rust

use std::collections::HashMap;

fn count_letters(word: &str) -> HashMap<char, usize> {
    let mut counts = HashMap::new();
    for ch in word.chars() {
        *counts.entry(ch).or_insert(0) += 1;
    }
    counts
}

fn are_anagrams(word1: &str, word2: &str) -> bool {
    if word1.len() != word2.len() {
        return false;
    }
    let count1 = count_letters(word1);
    let count2 = count_letters(word2);
    count1 == count2
}

fn main() {
    let word1 = "listen";
    let word2 = "silent";
    if are_anagrams(word1, word2) {
        println!("{} and {} are anagrams", word1, word2);
    } else {
        println!("{} and {} are NOT anagrams", word1, word2);
    }
}

for ch in word.chars() { *counts.entry(ch).or_insert(0) += 1; }

Count each letter's occurrences in the word

if word1.len() != word2.len() { return false; }

Quick check: if lengths differ, can't be anagrams

count1 == count2

Compare letter counts to confirm anagram status

Output

listen and silent are anagrams

Complexity Analysis

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

Space: O(1) because the letter count map size is limited by alphabet size, not input length

vs Alternative: Sorting both words takes O(n log n), so counting letters is faster for large inputs

Edge Cases

Empty strings

Returns true because two empty words have the same letters (none)

DSA Rust

if word1.len() != word2.len() { return false; }

Different lengths

Returns false immediately without counting letters

DSA Rust

if word1.len() != word2.len() { return false; }

Words with repeated letters

Counts ensure repeated letters match exactly

DSA Rust

*counts.entry(ch).or_insert(0) += 1;

When to Use This Pattern

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

Common Mistakes

Mistake: Only sorting one word and comparing to the other without sorting it
Fix: Sort both words before comparing or use letter counts for both

Mistake: Ignoring letter case or spaces
Fix: Normalize input by converting to lowercase and removing spaces before checking

Summary

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

Use when you want to know if two words are anagrams quickly and efficiently.

Counting letters and comparing counts is faster and simpler than sorting for this problem.

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 anagram definition

   Anagrams are words or phrases made by rearranging letters of another, so character frequency must match.

2. Step 2: Compare character frequencies

   Checking if both strings have the same characters with the same counts confirms they are anagrams.

3. Final Answer:

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

4. Quick Check:

   Anagram check = same characters & frequency [OK]

Hint: Check if character counts match in both strings [OK]

Common Mistakes:

• Only comparing string lengths
• Ignoring character frequency
• Checking only first characters

2. Which Rust code snippet correctly sorts the characters of a string s to help check anagrams?

easy

A. let mut chars: Vec<char> = s.chars().collect(); chars.sort();

B. let chars = s.sort();

C. let chars = s.chars().sorted();

D. let chars = s.to_vec().sort();

Solution

1. Step 1: Collect characters into a vector

   Use s.chars().collect() to get a vector of characters from the string.

2. Step 2: Sort the vector in place

   Call chars.sort() to sort characters alphabetically for comparison.

3. Final Answer:

   let mut chars: Vec<char> = s.chars().collect(); chars.sort(); -> Option A

4. Quick Check:

   Collect chars then sort vector [OK]

Hint: Collect chars into Vec then call sort() [OK]

Common Mistakes:

• Trying to sort string directly
• Using non-existent sorted() method
• Calling sort() on &str instead of Vec<char>

3. What is the output of this Rust code snippet?

fn main() {
    let s1 = "listen";
    let s2 = "silent";
    let mut v1: Vec<char> = s1.chars().collect();
    let mut v2: Vec<char> = s2.chars().collect();
    v1.sort();
    v2.sort();
    println!("{}", v1 == v2);
}

medium

A. Runtime panic

B. true

C. Compilation error

D. false

Solution

1. Step 1: Convert strings to char vectors and sort

   Both "listen" and "silent" are converted to vectors and sorted alphabetically.

2. Step 2: Compare sorted vectors

   Sorted vectors for both strings become ['e', 'i', 'l', 'n', 's', 't'], so they are equal.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Sorted chars equal means anagrams [OK]

Hint: Sort both strings and compare vectors [OK]

Common Mistakes:

• Expecting false because strings differ
• Confusing sorting with original order
• Thinking println! prints vectors directly

4. Identify the bug in this Rust function that checks if two strings are anagrams:

fn are_anagrams(s1: &str, s2: &str) -> bool {
    let mut v1: Vec<char> = s1.chars().collect();
    let mut v2: Vec<char> = s2.chars().collect();
    v1.sort();
    v2.sort();
    v1 == v2
}

fn main() {
    println!("{}", are_anagrams("abc", "cba"));
}

medium

A. Using == operator on vectors causes error

B. Missing mutable keyword for vectors

C. Should compare lengths before sorting

D. No bug, function works correctly

Solution

1. Step 1: Review vector creation and sorting

   Vectors are mutable and sorted correctly using v1.sort() and v2.sort().

2. Step 2: Check comparison and usage

   Comparing vectors with == is valid and returns true if sorted characters match.

3. Final Answer:

   No bug, function works correctly -> Option D

4. Quick Check:

   Sorting and comparing vectors works fine [OK]

Hint: Sorting vectors and comparing is valid in Rust [OK]

Common Mistakes:

• Thinking == can't compare vectors
• Assuming length check is mandatory
• Forgetting mut keyword (but it's present here)

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

hard

A. Sort strings without changing case or removing spaces

B. Compare strings directly after trimming spaces only

C. Convert both strings to lowercase, remove spaces, then sort and compare characters

D. Check if lengths match after removing spaces only

Solution

1. Step 1: Normalize strings by lowering case and removing spaces

   Convert both strings to lowercase and remove all spaces to ignore case and whitespace differences.

2. Step 2: Sort characters and compare

   Sort the cleaned character vectors and compare them to confirm anagram status.

3. Final Answer:

   Convert both strings to lowercase, remove spaces, then sort and compare characters -> Option C

4. Quick Check:

   Normalize case and spaces before sorting [OK]

Hint: Lowercase and remove spaces before sorting [OK]

Common Mistakes:

• Ignoring case differences
• Not removing spaces
• Comparing raw strings directly