First Non Repeating Character Using Hash in DSA Typescript

Mental Model

We want to find the first character in a string that appears only once by counting how many times each character shows up.

Analogy: Imagine a classroom where each student raises their hand once. We want to find the first student who raised their hand only once, ignoring those who raised it multiple times.

string: h -> e -> l -> l -> o -> null
hash: { h: 1, e: 1, l: 2, o: 1 }
↑ first unique char is 'h'

Dry Run Walkthrough

Input: string: "swiss"

Goal: Find the first character that appears only once in the string

Step 1: Count frequency of 's'

hash: { s: 1 }

Why: We start counting characters to know how many times each appears

Step 2: Count frequency of 'w'

hash: { s: 1, w: 1 }

Why: Add next character count

Step 3: Count frequency of 'i'

hash: { s: 1, w: 1, i: 1 }

Why: Add next character count

Step 4: Count frequency of 's' again

hash: { s: 2, w: 1, i: 1 }

Why: Increase count for repeated character

Step 5: Count frequency of 's' again

hash: { s: 3, w: 1, i: 1 }

Why: Increase count for repeated character

Step 6: Check characters in order to find first with count 1

string: s -> w -> i -> s -> s -> null
hash: { s: 3, w: 1, i: 1 }
first unique char found: 'w'

Why: We want the first character that appears only once

Result:

w

Annotated Code

DSA Typescript

class FirstNonRepeatingChar {
  static findFirstUniqueChar(s: string): string {
    const charCount: Record<string, number> = {};
    // Count frequency of each character
    for (const ch of s) {
      charCount[ch] = (charCount[ch] ?? 0) + 1;
    }
    // Find first character with count 1
    for (const ch of s) {
      if (charCount[ch] === 1) {
        return ch;
      }
    }
    return '';
  }
}

// Driver code
const input = "swiss";
const result = FirstNonRepeatingChar.findFirstUniqueChar(input);
console.log(result);

for (const ch of s) { charCount[ch] = (charCount[ch] ?? 0) + 1; }

Count frequency of each character in the string

for (const ch of s) { if (charCount[ch] === 1) { return ch; } }

Find and return the first character with frequency 1

Output

w

Complexity Analysis

Time: O(n) because we scan the string twice: once to count and once to find the first unique character

Space: O(k) where k is the number of unique characters, because we store counts in a hash

vs Alternative: Compared to checking each character by scanning the string repeatedly (O(n^2)), this hash method is much faster

Edge Cases

Empty string

Returns empty string since no characters exist

DSA Typescript

return '';

All characters repeated

Returns empty string because no unique character found

DSA Typescript

return '';

Single character string

Returns that character as it is unique

DSA Typescript

if (charCount[ch] === 1) { return ch; }

When to Use This Pattern

When asked to find the first unique or non-repeating element in a sequence, use a hash map to count frequencies and then scan to find the first with count one.

Common Mistakes

Mistake: Checking uniqueness by scanning the string inside a loop for each character (O(n^2))
Fix: Use a hash map to count frequencies first, then scan once to find the first unique character

Summary

Finds the first character in a string that appears only once using a hash map.

Use when you need to quickly identify the first unique character in a string.

Count all characters first, then find the first with count one.

Practice

1. What is the main purpose of using a hash (like a dictionary or map) to find 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 remove duplicate characters from the string

Solution

1. Step 1: Understand the role of a hash in frequency counting

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

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

   By checking the counts in order, 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 counts characters = To count the frequency of each character efficiently [OK]

Hint: Use a hash to count characters, then find count 1 [OK]

Common Mistakes:

• Thinking hash sorts characters
• Trying to reverse string instead
• Assuming hash removes duplicates

2. Which of the following TypeScript code snippets correctly initializes a hash map to store character counts?

easy

A. const charCount = new Set<string>();

B. const charCount = new Array();

C. const charCount = new Map();

D. const charCount = new Object<number>();

Solution

1. Step 1: Identify correct TypeScript syntax for a map

   TypeScript uses Map to create a hash map. Here, keys are strings and values are numbers.

2. Step 2: Check each option for correctness

   const charCount = new Map(); uses Map(), which is correct. Options A, B, and D use incorrect types or structures.

3. Final Answer:

   const charCount = new Map<string, number>(); -> Option C

4. Quick Check:

   Map<string, number> is correct syntax [OK]

Hint: Use Map() to store char counts [OK]

Common Mistakes:

• Using Array instead of Map
• Using Set which stores only keys
• Incorrect Object initialization

3. What will be the output of the following TypeScript code?

function firstNonRepeatingChar(s: string): string {
  const count = new Map();
  for (const ch of s) {
    count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  for (const ch of s) {
    if (count.get(ch) === 1) return ch;
  }
  return '_';
}
console.log(firstNonRepeatingChar('swiss'));

medium

A. '_'

B. 's'

C. 'i'

D. 'w'

Solution

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

   Characters: s(3), w(1), i(1). The map stores these counts.

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

   Order: 's' (count 3), 'w' (count 1), 'i' (count 1). The first with count 1 is 'w'.

3. Final Answer:

   'w' -> Option D

4. Quick Check:

   First unique char in 'swiss' = 'w' [OK]

Hint: Check counts in order, first with 1 is answer [OK]

Common Mistakes:

• Choosing first character without checking count
• Confusing 'i' and 'w'
• Returning '_' when unique char exists

4. Identify the bug in this TypeScript function to find the first non-repeating character:

function firstNonRepeatingChar(s: string): string {
  const count = new Map();
  for (let i = 0; i <= s.length; i++) {
    const ch = s[i];
    count.set(ch, (count.get(ch) ?? 0) + 1);
  }
  for (const ch of s) {
    if (count.get(ch) === 1) return ch;
  }
  return '_';
}

medium

A. Map should be initialized with Object instead of Map

B. Loop condition should be i < s.length, not i <= s.length

C. Return '_' should be inside the first loop

D. Use 'for...in' instead of 'for...of' for string iteration

Solution

1. Step 1: Check the for loop boundary

   The loop runs from i = 0 to i <= s.length, which accesses s[s.length], an undefined index causing error.

2. Step 2: Correct loop condition

   Change condition to i < s.length to avoid out-of-bounds access and correctly count characters.

3. Final Answer:

   Loop condition should be i < s.length, not i <= s.length -> Option B

4. Quick Check:

   Loop boundary off by one error [OK]

Hint: Use i < length, not i <= length in loops [OK]

Common Mistakes:

• Off-by-one error in loop condition
• Misusing Map initialization
• Wrong loop type for string iteration

5. Given the string 'aabbccddeeffg', which modification to the hash-based approach will correctly return the first non-repeating character when some characters appear multiple times and some only once?

hard

A. After counting, iterate the string and return the first character with count 1

B. Sort the string and return the first character

C. Return the character with the highest count from the hash

D. Return the last character in the string regardless of counts

Solution

1. Step 1: Count frequencies of all characters

   Use a hash map to count how many times each character appears in the string.

2. Step 2: Iterate string in original order to find first count 1

   Check each character in order; the first with count 1 is the first non-repeating character.

3. Final Answer:

   After counting, iterate the string and return the first character with count 1 -> Option A

4. Quick Check:

   Count then check order for first unique char [OK]

Hint: Count all, then find first with count 1 in order [OK]

Common Mistakes:

• Sorting string loses original order
• Returning highest count instead of unique
• Ignoring character order in result