First Non Repeating Character Using Hash in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind finding the first non-repeating character using a hash?

Use a hash map (dictionary) to count the frequency of each character, then find the first character with a count of 1.

beginner

Why do we need two passes over the string when using a hash to find the first non-repeating character?

First pass counts characters, second pass finds the first character with count 1 to maintain original order.

beginner

In Go, which data structure is commonly used as a hash map for counting characters?

A map with key type 'rune' and value type 'int' is used to count character frequencies.

beginner

What should be returned if all characters in the string repeat?

Return a special value like -1 or an empty character to indicate no non-repeating character found.

intermediate

How does using a hash map improve efficiency compared to checking each character against all others?

Hash map counting reduces time complexity from O(n²) to O(n) by avoiding repeated comparisons.

What is the time complexity of finding the first non-repeating character using a hash map?

A O(1)

B O(n²)

C O(log n)

D O(n)

Counting characters and then scanning once each is O(n) total.

Which Go data type is best for keys when counting characters in a string?

A rune

B int

C string

D byte

Rune represents Unicode code points, suitable for characters.

What does a count of 1 in the hash map indicate for a character?

A Character repeats

B Character appears once

C Character is last

D Character is first

Count 1 means the character appears only once.

If the input string is empty, what should the function return?

A First character

B Zero

C -1 or empty

D Error

No characters means no non-repeating character.

Why do we use two passes over the string in this algorithm?

A To count and then find first unique

B To sort characters

C To reverse the string

D To remove duplicates

First pass counts frequencies, second finds first unique.

Explain how to find the first non-repeating character in a string using a hash map.

Think about counting first, then scanning.

Describe why using a hash map is more efficient than nested loops for this problem.

Focus on how hash map reduces repeated work.

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