Anagram Check Techniques in DSA Rust - 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 one of three techniques: sorting, counting characters, or using a hash map to compare character frequencies.

Execution Sample

DSA Rust

fn are_anagrams(s1: &str, s2: &str) -> bool {
    if s1.len() != s2.len() { return false; }
    let mut v1: Vec<char> = s1.chars().collect();
    let mut v2: Vec<char> = s2.chars().collect();
    v1.sort_unstable();
    v2.sort_unstable();
    v1 == v2
}

This code checks if two strings are anagrams by sorting their characters and comparing the sorted results.

Execution Table

Step	Operation	String 1 State	String 2 State	Comparison	Result
1	Check length	"listen" (6 chars)	"silent" (6 chars)	6 == 6	Continue
2	Convert to char vectors	[l, i, s, t, e, n]	[s, i, l, e, n, t]	N/A	Continue
3	Sort vectors	[e, i, l, n, s, t]	[e, i, l, n, s, t]	N/A	Continue
4	Compare sorted vectors	[e, i, l, n, s, t]	[e, i, l, n, s, t]	Equal	Anagrams
5	End	N/A	N/A	N/A	Return true

💡 Strings are anagrams because sorted character arrays are equal.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
s1	"listen"	"listen"	"listen"	"listen"
s2	"silent"	"silent"	"silent"	"silent"
v1	[]	[l, i, s, t, e, n]	[e, i, l, n, s, t]	[e, i, l, n, s, t]
v2	[]	[s, i, l, e, n, t]	[e, i, l, n, s, t]	[e, i, l, n, s, t]

Key Moments - 3 Insights

Why do we check string lengths first before sorting or counting?

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

Why do we sort the characters before comparing?

Sorting arranges characters in order, so if both sorted lists match (Step 4), the strings have the same characters in the same counts.

Can we compare strings directly without sorting?

No, because characters can be in different orders. Sorting or counting ensures order doesn't affect the comparison.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of v1 after Step 3?

A [l, i, s, t, e, n]

B [e, i, l, n, s, t]

C [s, i, l, e, n, t]

D []

💡 Hint

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

At which step does the code decide the strings are anagrams?

A Step 4

B Step 2

C Step 1

D Step 5

💡 Hint

Look for the 'Comparison' column where sorted vectors are equal.

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

A The code would continue sorting

B The code would compare sorted vectors

C The code would return false immediately

D The code would crash

💡 Hint

See Step 1 where length check is done.

Concept Snapshot

Anagram Check Techniques:
1. Check if strings have equal length.
2. Sort both strings and compare sorted results.
3. Alternatively, count characters using arrays or hash maps.
4. If counts or sorted arrays match, strings are anagrams.
5. Early length check saves time.
6. Sorting method is simple and effective for small strings.

Full Transcript

To check if two strings are anagrams, first compare their lengths. If lengths differ, they cannot be anagrams. If lengths are equal, convert each string into a list of characters. Sort these lists alphabetically. Then compare the sorted lists. If they are identical, the strings are anagrams. This method works because sorting arranges characters in order, making it easy to compare. Alternatively, counting characters using arrays or hash maps can also verify anagrams by comparing character frequencies. Early length check helps avoid unnecessary work. This approach is simple and effective for beginners and small 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 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