First Non Repeating Character Using Hash in DSA Go - Execution Trace

Concept Flow - First Non Repeating Character Using Hash

Start with input string

↓

Create empty hash map for counts

↓

For each char in string

↓

Increment char count in hash

↓

For each char in string

↓

Check if count == 1?

No→Continue

Yes↓

Return this char as first non repeating

↓

If none found, return special value

We count each character's occurrences using a hash map, then find the first character with count one.

Execution Sample

DSA Go

func firstNonRepeatingChar(s string) rune {
  counts := make(map[rune]int)
  for _, ch := range s {
    counts[ch]++
  }
  for _, ch := range s {
    if counts[ch] == 1 {
      return ch
    }
  }
  return '\u0000'
}

This code finds the first character in a string that appears only once using a hash map.

Execution Table

Step	Operation	Character Processed	Hash Map State	Action	Visual State
1	Initialize hash map	-	{}	Create empty map	[]
2	Count char	'g'	{'g':1}	Add 'g' count=1	[g:1]
3	Count char	'o'	{'g':1, 'o':1}	Add 'o' count=1	[g:1, o:1]
4	Count char	'o'	{'g':1, 'o':2}	Increment 'o' count=2	[g:1, o:2]
5	Count char	'd'	{'g':1, 'o':2, 'd':1}	Add 'd' count=1	[g:1, o:2, d:1]
6	Count char	'o'	{'g':1, 'o':3, 'd':1}	Increment 'o' count=3	[g:1, o:3, d:1]
7	Count char	'g'	{'g':2, 'o':3, 'd':1}	Increment 'g' count=2	[g:2, o:3, d:1]
8	Count char	'l'	{'g':2, 'o':3, 'd':1, 'l':1}	Add 'l' count=1	[g:2, o:3, d:1, l:1]
9	Count char	'e'	{'g':2, 'o':3, 'd':1, 'l':1, 'e':1}	Add 'e' count=1	[g:2, o:3, d:1, l:1, e:1]
10	Find first non repeating	'g'	{'g':2, 'o':3, 'd':1, 'l':1, 'e':1}	Count=2, skip	[g:2, o:3, d:1, l:1, e:1]
11	Find first non repeating	'o'	{'g':2, 'o':3, 'd':1, 'l':1, 'e':1}	Count=3, skip	[g:2, o:3, d:1, l:1, e:1]
12	Find first non repeating	'o'	{'g':2, 'o':3, 'd':1, 'l':1, 'e':1}	Count=3, skip	[g:2, o:3, d:1, l:1, e:1]
13	Find first non repeating	'd'	{'g':2, 'o':3, 'd':1, 'l':1, 'e':1}	Count=1, return 'd'	[g:2, o:3, d:1, l:1, e:1]
14	End	-	-	Return 'd' as first non repeating	[g:2, o:3, d:1, l:1, e:1]

💡 Found 'd' with count 1 at step 13, so returned as first non repeating character.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 9	Final
counts	{}	{'g':1}	{'g':1, 'o':2}	{'g':2, 'o':3, 'd':1}	{'g':2, 'o':3, 'd':1, 'l':1, 'e':1}	{'g':2, 'o':3, 'd':1, 'l':1, 'e':1}
current_char	-	'g'	'o'	'g'	'e'	'd'

Key Moments - 3 Insights

Why do we need two loops instead of one?

The first loop counts all characters (see steps 2-9). The second loop finds the first character with count 1 (steps 10-13). Doing both in one loop would miss the order.

What if the string has no non repeating characters?

If no character has count 1, the second loop finishes without returning (not shown here). Then the function returns '\u0000' as a special value (step 14).

Why do we use a hash map for counts?

The hash map lets us count characters quickly in O(n) time, instead of checking each character multiple times.

Visual Quiz - 3 Questions

Look at the execution table, what is the count of 'o' after step 6?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'Hash Map State' column at step 6 in the execution table.

At which step does the function find the first non repeating character?

A Step 10

B Step 12

C Step 13

D Step 14

💡 Hint

Look for the step where 'Count=1, return' action happens in the execution table.

If the input string was 'aabbcc', what would the function return?

A Special value '\u0000'

B 'b'

C 'a'

D 'c'

💡 Hint

Refer to the key moment about no non repeating characters and the final return value.

Concept Snapshot

First Non Repeating Character Using Hash

- Use a hash map to count occurrences of each character.
- First loop: count all characters.
- Second loop: find first character with count 1.
- Return that character or special value if none found.
- Runs in O(n) time with O(n) space.

Full Transcript

This concept finds the first character in a string that does not repeat. We use a hash map to count how many times each character appears. First, we loop through the string and update counts. Then, we loop again to find the first character with count one. If found, we return it. Otherwise, we return a special value indicating no such character exists. This approach is efficient and keeps track of character order.

Practice

1. What is the main purpose of using a hash map in finding the first non-repeating character in a string?

easy

A. To count the frequency of each character efficiently

B. To sort the characters alphabetically

C. To reverse the string quickly

D. To store characters in a linked list

Solution

1. Step 1: Understand the role of hash map

   A hash map stores each character as a key and counts how many times it appears in the string.

2. Step 2: Use frequency to find non-repeating character

   By checking the counts, we can find the first character with count 1, which is the first non-repeating character.

3. Final Answer:

   To count the frequency of each character efficiently -> Option A

4. Quick Check:

   Hash map counts characters = frequency count [OK]

Hint: Hash maps count characters fast to find unique ones [OK]

Common Mistakes:

• Thinking hash map sorts characters
• Using hash map to reverse string
• Confusing hash map with linked list

2. Which of the following Go code snippets correctly declares a hash map to store character counts for a string?

easy

A. counts := make(map[string]int)

B. counts := make([]int, len(s))

C. counts := make(map[int]string)

D. counts := make(map[rune]int)

Solution

1. Step 1: Identify correct map key type for characters

   In Go, characters from strings are best represented as 'rune' type, so map[rune]int is correct for counting characters.

2. Step 2: Check other options

   counts := make(map[string]int) uses string as key which is incorrect for single characters; counts := make(map[int]string) reverses key and value types; counts := make([]int, len(s)) is a slice, not a map.

3. Final Answer:

   counts := make(map[rune]int) -> Option D

4. Quick Check:

   Use map[rune]int for character counts in Go [OK]

Hint: Use map[rune]int to count characters in Go strings [OK]

Common Mistakes:

• Using map[string]int for single characters
• Confusing slices with maps
• Using wrong key-value types in map

3. What will be the output of the following Go code snippet?

package main
import "fmt"
func main() {
    s := "swiss"
    counts := make(map[rune]int)
    for _, ch := range s {
        counts[ch]++
    }
    for _, ch := range s {
        if counts[ch] == 1 {
            fmt.Println(string(ch))
            break
        }
    }
}

medium

A. w

B. s

C. i

D. No output

Solution

1. Step 1: Count character frequencies in "swiss"

   Characters and counts: 's' = 3, 'w' = 1, 'i' = 1.

2. Step 2: Find first character with count 1 in order

   Order in string: 's'(3), 'w'(1), 'i'(1), 's'(3), 's'(3). First with count 1 is 'w'.

3. Final Answer:

   w -> Option A

4. Quick Check:

   First unique char in "swiss" is 'w' [OK]

Hint: Check counts in string order; first count 1 is answer [OK]

Common Mistakes:

• Picking 's' which repeats
• Choosing 'i' ignoring order
• Expecting no output

4. Identify the bug in this Go code that tries to find the first non-repeating character:

package main
import "fmt"
func main() {
    s := "hello"
    counts := make(map[rune]int)
    for i := 0; i < len(s); i++ {
        counts[rune(s[i])] = counts[rune(s[i])] + 1
    }
    for i := 0; i < len(s); i++ {
        if counts[rune(s[i])] == 1 {
            fmt.Println(s[i])
            break
        }
    }
}

medium

A. Loop should use range instead of index

B. Map key should be string, not rune

C. Printing s[i] prints byte, not character

D. Counts map is not initialized

Solution

1. Step 1: Check how character is printed

   Printing s[i] prints a byte as integer, not the character itself.

2. Step 2: Fix printing to convert byte to string

   Use fmt.Println(string(s[i])) to print the character properly.

3. Final Answer:

   Printing s[i] prints byte, not character -> Option C

4. Quick Check:

   Print string(s[i]) to show character, not byte [OK]

Hint: Convert byte to string when printing characters [OK]

Common Mistakes:

• Ignoring printing type mismatch
• Changing map key type unnecessarily
• Not initializing map (already done)

5. Given the string "aabbccdde", which code modification will correctly find the first non-repeating character using a hash map in Go, considering the string may contain Unicode characters?

hard

A. Use map[byte]int and iterate with 'for i := 0; i < len(s); i++'

B. Use map[rune]int and iterate with 'for _, ch := range s' to count frequencies

C. Use map[string]int and split string into substrings of length 2

D. Use map[int]int and convert characters to ASCII codes manually

Solution

1. Step 1: Choose correct map key type for Unicode

   Using map[rune]int allows counting Unicode characters correctly, unlike byte which only handles ASCII.

2. Step 2: Use range loop to iterate runes

   Using 'for _, ch := range s' iterates over runes, correctly handling multi-byte Unicode characters.

3. Final Answer:

   Use map[rune]int and iterate with 'for _, ch := range s' to count frequencies -> Option B

4. Quick Check:

   map[rune]int + range loop handles Unicode correctly [OK]

Hint: Use rune keys and range loop for Unicode-safe counting [OK]

Common Mistakes:

• Using byte keys breaks Unicode characters
• Splitting string incorrectly into substrings
• Using int keys without clear mapping