First Non Repeating Character Using Hash in DSA Typescript - Deep Dive

Overview - First Non Repeating Character Using Hash

What is it?

The First Non Repeating Character problem asks us to find the first character in a string that does not repeat anywhere else. Using a hash means we use a data structure to count how many times each character appears. This helps us quickly find the character that appears only once and appears earliest in the string. It is a common problem to understand how to count and track elements efficiently.

Why it matters

Without this concept, finding unique characters would require checking each character against all others repeatedly, which is slow and inefficient. Using a hash to count characters makes the process fast and practical, especially for long texts or real-time applications like spell checkers or input validation. It teaches how to use simple data structures to solve everyday problems efficiently.

Where it fits

Before this, learners should understand basic strings and loops. After this, they can learn about more complex hashing techniques, frequency counting in arrays, or sliding window problems. This topic builds a foundation for understanding hash maps and their power in solving counting and lookup problems.

Mental Model

Core Idea

Count how many times each character appears, then find the first one that appears exactly once.

Think of it like...

Imagine a classroom where each student raises their hand once for every time they spoke. The teacher looks for the first student who raised their hand only once to answer a question.

String:  a  b  c  a  b  d  e
Count:   2  2  1  2  2  1  1
First non-repeating character is 'c' at index 2

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Statement

Concept: Learn what it means for a character to be non-repeating and why order matters.

Given a string, we want to find the first character that appears only once. For example, in 'swiss', 'w' is the first non-repeating character because 's' repeats multiple times.

Result

You understand the goal: find the earliest unique character in a string.

Understanding the problem clearly is the first step to solving it correctly.

2

Foundation

Using a Hash Map to Count Characters

Concept: Introduce a hash map (object/dictionary) to count how many times each character appears.

We create an empty hash map. We loop through the string, and for each character, we increase its count in the map. For example, for 'hello', counts would be {h:1, e:1, l:2, o:1}.

Result

You get a frequency count of all characters in the string.

Counting frequencies with a hash map is a simple and efficient way to track occurrences.

3

Intermediate

Finding the First Unique Character

🤔Before reading on: Do you think we should check characters in the order they appear or in the order of the hash map keys? Commit to your answer.

Concept: After counting, we must check characters in the original string order to find the first with count 1.

We loop through the string again. For each character, we check its count in the hash map. The first character with count 1 is our answer.

Result

You find the first non-repeating character efficiently.

Order matters: checking characters in string order ensures the earliest unique character is found.

4

Intermediate

Handling Edge Cases and Empty Strings

🤔Before reading on: What should the function return if all characters repeat or the string is empty? Commit to your answer.

Concept: Decide what to return when no unique character exists or input is empty.

If no character has count 1, we can return a special value like -1 or an empty string. For empty input, return the same special value.

Result

Your function gracefully handles all inputs without errors.

Thinking about edge cases prevents bugs and unexpected crashes.

5

Advanced

Implementing the Solution in TypeScript

🤔Before reading on: Can you predict the output of the code for input 'aabbcdde'? Commit to your answer.

Concept: Write complete, runnable TypeScript code using a hash map to solve the problem.

const firstNonRepeatingChar = (s: string): string => { const counts: {[key: string]: number} = {}; for (const char of s) { counts[char] = (counts[char] || 0) + 1; } for (const char of s) { if (counts[char] === 1) return char; } return ''; }; console.log(firstNonRepeatingChar('aabbcdde')); // Output: 'c'

Result

Output: 'c'

Writing code solidifies understanding and shows how theory becomes practice.

6

Expert

Optimizing for Performance and Memory

🤔Before reading on: Do you think we can find the first non-repeating character in a single pass? Commit to your answer.

Concept: Explore if the problem can be solved in one pass or with less memory, and understand trade-offs.

One pass is tricky because we don't know counts until we see all characters. Using two passes is simple and efficient. For very large inputs, we can optimize by using fixed-size arrays for known character sets (like ASCII) instead of hash maps, saving memory and speeding up access.

Result

You understand why two passes are common and when to optimize for memory or speed.

Knowing trade-offs helps write code that fits real-world constraints.

Under the Hood

The hash map stores character keys with their counts as values. When looping through the string, each character's count is incremented in constant time. The second loop checks counts in order, ensuring the first unique character is found. Internally, hash maps use arrays and hashing functions to achieve fast lookups and updates.

Why designed this way?

Hash maps provide average constant time complexity for insertions and lookups, making counting efficient. Two passes separate counting and searching, simplifying logic and avoiding complex state management. Alternatives like nested loops would be slower (quadratic time).

Input String:  a  b  c  a  b  d  e
               ↓  ↓  ↓  ↓  ↓  ↓  ↓
Hash Map:     {a:2, b:2, c:1, d:1, e:1}

Second Pass:
Check 'a' count=2 -> skip
Check 'b' count=2 -> skip
Check 'c' count=1 -> return 'c'

Myth Busters - 3 Common Misconceptions

Quick: Do you think the first character with count 1 is always the first unique character? Commit yes or no.

Common Belief: The first character with count 1 in the hash map keys is the first unique character.

Reality: Hash map keys have no guaranteed order; only the string's original order determines the first unique character.

Why it matters: Relying on hash map key order can cause wrong answers, especially in languages where object key order is not guaranteed.

Quick: Can you find the first non-repeating character in one pass? Commit yes or no.

Common Belief: It's possible to find the first non-repeating character in a single pass through the string.

Reality: You need at least two passes: one to count frequencies, one to find the first unique character, because you can't know if a character repeats until you see the whole string.

Why it matters: Trying to do it in one pass leads to complicated and error-prone code that may miss characters or give wrong results.

Quick: Does an empty string have a first non-repeating character? Commit yes or no.

Common Belief: An empty string has a first non-repeating character, which is an empty character or null.

Reality: An empty string has no characters, so no non-repeating character exists; the function should return a special value like '' or -1.

Why it matters: Not handling empty input causes runtime errors or incorrect outputs.

Expert Zone

1

Hash maps in JavaScript/TypeScript preserve insertion order for string keys, but relying on this is risky for cross-language compatibility.

2

Using fixed-size arrays for character counts is faster and uses less memory when the character set is known and small (like ASCII).

3

In Unicode strings, characters can be multiple code units; counting by code units may miscount some characters, requiring careful handling.

When NOT to use

If the input is extremely large and memory is limited, or if characters are from a huge Unicode set, consider streaming algorithms or probabilistic data structures like Bloom filters instead of full hash maps.

Production Patterns

This pattern is used in text processing, spell checkers, and input validation to quickly find unique tokens. It also appears in interview coding challenges to test understanding of hash maps and string manipulation.

Connections

Hash Map

Builds-on

Understanding how hash maps store and retrieve data efficiently is key to solving counting problems like this.

Frequency Counting

Same pattern

Counting how often items appear is a common pattern in many algorithms, from statistics to machine learning.

Inventory Management

Analogous real-world system

Just like counting items in a warehouse to find unique stock, counting characters helps identify unique elements in data.

Common Pitfalls

#1 Checking hash map keys directly to find the first unique character.

Wrong approach:

for (const char in counts) {
if (counts[char] === 1) return char;
}

Correct approach:

for (const char of s) {
if (counts[char] === 1) return char;
}

Root cause:

Hash map keys do not guarantee order; only the original string order ensures the first unique character.

#2 Returning a character before counting all frequencies.

Wrong approach:

for (const char of s) {
if (!seen[char]) return char;
seen[char] = true;
}

Correct approach:

First count all characters, then loop again to find the first with count 1.

Root cause:

You can't know if a character repeats until you see the whole string.

#3 Not handling empty strings or strings with no unique characters.

Wrong approach:

function firstNonRepeatingChar(s: string): string {
const counts = {};
for (const c of s) counts[c] = (counts[c] || 0) + 1;
for (const c of s) {
if (counts[c] === 1) return c;
}
// no return here
}

Correct approach:

function firstNonRepeatingChar(s: string): string {
const counts = {};
for (const c of s) counts[c] = (counts[c] || 0) + 1;
for (const c of s) {
if (counts[c] === 1) return c;
}
return '';
}

Root cause:

Missing a return for the case when no unique character exists causes undefined behavior.

Key Takeaways

The first non-repeating character is found by counting all characters and then checking them in original order.

Hash maps provide an efficient way to count frequencies with average constant time operations.

Order matters: always check characters in the string's order, not hash map key order.

Edge cases like empty strings or no unique characters must be handled explicitly.

Understanding trade-offs between passes and memory helps write practical, efficient code.

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