Anagram Check Techniques in DSA Go - Execution Trace

Concept Flow - Anagram Check Techniques

Start with two strings

↓

Check length equal?

No→Return False

Yes↓

Choose technique

↓

Sort both

↓

Compare sorted

↓

Return True/False based on equality

↓

End

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

Execution Sample

DSA Go

func areAnagrams(s1, s2 string) bool {
  if len(s1) != len(s2) {
    return false
  }
  count := make(map[rune]int)
  for _, ch := range s1 {
    count[ch]++
  }
  for _, ch := range s2 {
    count[ch]--
    if count[ch] < 0 {
      return false
    }
  }
  return true
}

Checks if two strings are anagrams by counting character frequencies using a map.

Execution Table

Step	Operation	Character Processed	Map State	Condition	Result
1	Check length	s1='listen', s2='silent'	{}	len(s1)==len(s2)? True	Continue
2	Count chars in s1	l	{'l':1}	N/A	Continue
3	Count chars in s1	i	{'l':1, 'i':1}	N/A	Continue
4	Count chars in s1	s	{'l':1, 'i':1, 's':1}	N/A	Continue
5	Count chars in s1	t	{'l':1, 'i':1, 's':1, 't':1}	N/A	Continue
6	Count chars in s1	e	{'l':1, 'i':1, 's':1, 't':1, 'e':1}	N/A	Continue
7	Count chars in s1	n	{'l':1, 'i':1, 's':1, 't':1, 'e':1, 'n':1}	N/A	Continue
8	Decrease count for s2	s	{'l':1, 'i':1, 's':0, 't':1, 'e':1, 'n':1}	count[s]>=0? True	Continue
9	Decrease count for s2	i	{'l':1, 'i':0, 's':0, 't':1, 'e':1, 'n':1}	count[i]>=0? True	Continue
10	Decrease count for s2	l	{'l':0, 'i':0, 's':0, 't':1, 'e':1, 'n':1}	count[l]>=0? True	Continue
11	Decrease count for s2	e	{'l':0, 'i':0, 's':0, 't':1, 'e':0, 'n':1}	count[e]>=0? True	Continue
12	Decrease count for s2	n	{'l':0, 'i':0, 's':0, 't':1, 'e':0, 'n':0}	count[n]>=0? True	Continue
13	Decrease count for s2	t	{'l':0, 'i':0, 's':0, 't':0, 'e':0, 'n':0}	count[t]>=0? True	Continue
14	All counts zero?	N/A	{'l':0, 'i':0, 's':0, 't':0, 'e':0, 'n':0}	Yes	Return True

💡 All character counts matched, so strings are anagrams.

Variable Tracker

Variable	Start	After Step 7	After Step 13	Final
count map	{}	{'l':1, 'i':1, 's':1, 't':1, 'e':1, 'n':1}	{'l':0, 'i':0, 's':0, 't':0, 'e':0, 'n':0}	{'l':0, 'i':0, 's':0, 't':0, 'e':0, 'n':0}
len(s1)	6	6	6	6
len(s2)	6	6	6	6

Key Moments - 3 Insights

Why do we check if lengths are equal before counting characters?

Because if lengths differ, they cannot be anagrams. This is shown in step 1 where length check stops early if false.

Why do we return false if count[ch] < 0 during decrement?

It means s2 has more of character ch than s1, so they can't be anagrams. This is checked in steps 8-13.

Why do we not need to check counts after the loop explicitly?

Because if any count was negative, we returned false early. If loop finishes, all counts are zero, so strings are anagrams (step 14).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the count map state?

A {'l':1, 'i':1, 's':1, 't':1}

B {'l':1, 'i':1, 's':1}

C {'l':1, 'i':1, 's':1, 't':1, 'e':1}

D {'l':1, 'i':1}

💡 Hint

Check the 'Map State' column at step 5 in execution_table.

At which step does the condition 'count[ch] < 0' become true causing a false return?

A Step 8

B Step 14

C Never in this example

D Step 1

💡 Hint

Look at the 'Condition' and 'Result' columns in execution_table for steps 8-13.

If s2 had an extra 'x' character, how would the map state change at step 13?

A count['x'] would be -1 causing false return

B count['x'] would be 1 and return true

C No change in map state

D count['x'] would be 0

💡 Hint

Refer to how decrementing counts below zero triggers false in execution_table steps 8-13.

Concept Snapshot

Anagram Check Techniques:
- Check if strings have equal length first.
- Use sorting or character counting (map) to compare.
- Counting method: increment counts for s1, decrement for s2.
- If any count < 0 during decrement, return false.
- If all counts zero at end, strings are anagrams.

Full Transcript

This visual execution trace shows how to check if two strings are anagrams using character counting with a map. First, the code checks if the strings have the same length. If not, it returns false immediately. Then it counts each character in the first string by incrementing counts in a map. Next, it decrements counts for each character in the second string. If any count goes below zero, it means the second string has extra characters not in the first, so it returns false. If all counts are zero after processing both strings, it returns true, confirming the strings are anagrams. The execution table tracks each step, showing the map state and conditions checked. Key moments clarify why length check is important, why negative counts cause early exit, and why no final check is needed after the loop. The quiz questions test understanding of map states and conditions during execution.

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 vowels only

Solution

1. Step 1: Understand anagram definition

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

2. Step 2: Compare character frequency

   Checking if two strings have the same frequency of each character confirms if they are anagrams.

3. Final Answer:

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

4. Quick Check:

   Character frequency equality = Anagram check [OK]

Hint: Check if sorted strings are equal [OK]

Common Mistakes:

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

2. Which Go code snippet correctly checks if two strings are anagrams by sorting?

easy

A. sort.Strings([]string{s1, s2}); return s1 == s2

B. s1Sorted := sort.Strings(strings.Split(s1, "")); s2Sorted := sort.Strings(strings.Split(s2, "")); return s1Sorted == s2Sorted

C. s1Sorted := strings.Split(s1, ""); sort.Strings(s1Sorted); s2Sorted := strings.Split(s2, ""); sort.Strings(s2Sorted); return strings.Join(s1Sorted, "") == strings.Join(s2Sorted, "")

D. return s1 == s2

Solution

1. Step 1: Split strings into slices of characters

   Use strings.Split(s, "") to get slice of characters for sorting.

2. Step 2: Sort slices and join back to strings

   Sort each slice with sort.Strings and join with strings.Join to compare sorted strings.

3. Final Answer:

   Splitting, sorting slices, then joining for comparison -> Option C

4. Quick Check:

   Sort slices and join = Correct anagram check [OK]

Hint: Split, sort slices, join, then compare [OK]

Common Mistakes:

• Trying to sort strings directly (not allowed)
• Comparing unsorted strings
• Using sort.Strings on whole string instead of slice

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

func areAnagrams(s1, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    count := make(map[rune]int)
    for _, ch := range s1 {
        count[ch]++
    }
    for _, ch := range s2 {
        count[ch]--
        if count[ch] < 0 {
            return false
        }
    }
    return true
}

fmt.Println(areAnagrams("listen", "silent"))
fmt.Println(areAnagrams("hello", "bello"))

medium

A. true false

B. false true

C. true true

D. false false

Solution

1. Step 1: Count characters in first string

   Map counts characters in "listen": l=1, i=1, s=1, t=1, e=1, n=1.

2. Step 2: Decrease counts for second string and check negatives

   For "silent", counts decrease to zero without negatives, so true. For "bello", 'b' not in map or count negative, so false.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   Map count balance = true/false [OK]

Hint: Use map counts to verify character balance [OK]

Common Mistakes:

• Not checking length first
• Not returning false on negative count
• Confusing rune and byte iteration

4. Identify the bug in this Go function that checks anagrams:

func isAnagram(s1, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    count := make(map[rune]int)
    for i := 0; i < len(s1); i++ {
        count[rune(s1[i])]++
        count[rune(s2[i])]--
    }
    for _, v := range count {
        if v != 0 {
            return false
        }
    }
    return true
}

medium

A. Not checking string lengths before counting

B. Using rune conversion on byte indexing may miscount multibyte characters

C. Missing return statement at the end

D. Using map with int keys instead of rune keys

Solution

1. Step 1: Understand rune vs byte indexing in Go strings

   Indexing strings by byte (s1[i]) may split multibyte characters incorrectly, causing wrong rune counts.

2. Step 2: Identify correct iteration method

   Use range over string to get runes properly instead of byte indexing with rune conversion.

3. Final Answer:

   Using rune conversion on byte indexing may miscount multibyte characters -> Option B

4. Quick Check:

   Byte indexing ≠ rune iteration for Unicode [OK]

Hint: Use 'for _, r := range s' to handle runes correctly [OK]

Common Mistakes:

• Assuming byte indexing works for all characters
• Ignoring Unicode multibyte characters
• Not checking map values properly

5. Given a list of strings, which Go approach efficiently groups all anagrams together?

hard

A. Use string length as map key to group strings

B. Compare every pair of strings with nested loops checking character counts

C. Count vowels in each string and group by vowel count

D. Sort each string's characters and use the sorted string as a map key

Solution

1. Step 1: Understand grouping anagrams by sorted keys

   Sorting characters of each string creates a unique key for all anagrams, allowing grouping in a map efficiently.

2. Step 2: Compare with other methods

   Nested loops are slow (O(n²)), length or vowel count grouping is inaccurate for anagrams.

3. Final Answer:

   Sort each string's characters and use the sorted string as a map key -> Option D

4. Quick Check:

   Sorted string keys = efficient anagram grouping [OK]

Hint: Sort strings and group by sorted key [OK]

Common Mistakes:

• Using nested loops causing slow performance
• Grouping by length only misses anagrams
• Grouping by vowels ignores consonants