First Non Repeating Character Using Hash in DSA Javascript

Mental Model

We count how many times each letter appears, then find the first letter that appears only once.

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

string: "s: h -> e -> l -> l -> o -> null\ncount: {h:1, e:1, l:2, o:1}"

Dry Run Walkthrough

Input: string: "hello"

Goal: Find the first character in the string that does not repeat.

Step 1: Count characters: see 'h', add h:1

h:1

Why: We start counting each character's occurrences.

Step 2: Count characters: see 'e', add e:1

h:1, e:1

Why: Keep counting each character as we move forward.

Step 3: Count characters: see 'l', add l:1

h:1, e:1, l:1

Why: First 'l' counted.

Step 4: Count characters: see second 'l', update l:2

h:1, e:1, l:2

Why: Second 'l' increases count to 2.

Step 5: Count characters: see 'o', add o:1

h:1, e:1, l:2, o:1

Why: Count 'o' once.

Step 6: Scan string from start to find first char with count 1: 'h' count=1

h:1, e:1, l:2, o:1

Why: First non repeating character found at 'h'.

Result:

h is the first non repeating character

Annotated Code

DSA Javascript

class FirstNonRepeating {
  static findFirstNonRepeatingChar(str) {
    const count = {};
    // Count each character's frequency
    for (const ch of str) {
      count[ch] = (count[ch] ?? 0) + 1;
    }
    // Find first character with count 1
    for (const ch of str) {
      if (count[ch] === 1) {
        return ch;
      }
    }
    return null;
  }
}

// Driver code
const input = "hello";
const result = FirstNonRepeating.findFirstNonRepeatingChar(input);
console.log(result === null ? "No non repeating character" : result);

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

Count each character's frequency in the string.

for (const ch of str) { if (count[ch] === 1) { return ch; } }

Find and return the first character with frequency 1.

Output

h

Complexity Analysis

Time: O(n) because we scan the string twice but each scan is linear in string length n

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

vs Alternative: Naive approach checks each character against all others, O(n²), so hash counting is much faster.

Edge Cases

empty string

returns null because there is no character

DSA Javascript

return null;

all characters repeating

returns null because no character appears once

DSA Javascript

return null;

single character string

returns that character because it appears once

DSA Javascript

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

When to Use This Pattern

When you need to find the first unique element in a sequence, use a hash map to count frequencies and then scan to find the first unique.

Common Mistakes

Mistake: Returning the first character with count 1 without scanning in original order
Fix: Scan the string in original order to find the first character with count 1.

Mistake: Using nested loops to check uniqueness causing O(n²) time
Fix: Use a hash map to count frequencies in O(n) time.

Summary

Finds the first character in a string that does not repeat using a hash map.

Use when you need to identify the earliest unique character efficiently.

Count all characters first, then scan in order to find the first unique one.

Practice

1. What is the main purpose of using a hash (object) in finding the first non repeating character in a string?

easy

A. To reverse the string

B. To sort the characters alphabetically

C. To remove duplicate characters from the string

D. To count the frequency of each character in the string

Solution

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

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

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

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

3. Final Answer:

   To count the frequency of each character in the string -> Option D

4. Quick Check:

   Hash counts characters = Frequency count [OK]

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

Common Mistakes:

• Trying to sort characters instead of counting
• Ignoring character frequency
• Using hash to reverse string

2. Which of the following is the correct syntax to initialize an empty hash (object) in JavaScript for counting characters?

easy

A. let hash = [];

B. let hash = {};

C. let hash = ();

D. let hash = '';

Solution

1. Step 1: Identify JavaScript object syntax

   In JavaScript, curly braces {} create an empty object, which is used as a hash for key-value pairs.

2. Step 2: Confirm correct initialization

   Using let hash = {}; correctly initializes an empty object for counting characters.

3. Final Answer:

   let hash = {}; -> Option B

4. Quick Check:

   Empty object = {} [OK]

Hint: Use {} to create empty object for hash in JavaScript [OK]

Common Mistakes:

• Using [] which creates an array, not an object
• Using () which is invalid syntax
• Using empty string '' which is not an object

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

function firstNonRepeatingChar(str) {
  const hash = {};
  for (const ch of str) {
    hash[ch] = (hash[ch] || 0) + 1;
  }
  for (const ch of str) {
    if (hash[ch] === 1) return ch;
  }
  return '_';
}

console.log(firstNonRepeatingChar('swiss'));

medium

A. 'w'

B. 's'

C. 'i'

D. '_'

Solution

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

   Characters: s(3), w(1), i(1). Hash = {s:3, w:1, i:1}

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

   Order: s, w, i, s, s. First with count 1 is 'w'.

3. Final Answer:

   'w' -> Option A

4. Quick Check:

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

Hint: Check counts, then scan string for first count 1 char [OK]

Common Mistakes:

• Returning 's' which repeats
• Returning 'i' which is second unique
• Returning '_' which means no unique char

4. Identify the error in the following code snippet that tries to find the first non repeating character:

function firstNonRepeatingChar(str) {
  const hash = {};
  for (let i = 0; i <= str.length; i++) {
    const ch = str[i];
    hash[ch] = (hash[ch] || 0) + 1;
  }
  for (let i = 0; i < str.length; i++) {
    if (hash[str[i]] === 1) return str[i];
  }
  return '_';
}

medium

A. The hash is not initialized correctly

B. The second loop should use <= instead of <

C. The first loop uses <= instead of < causing undefined access

D. The return '_' is unreachable code

Solution

1. Step 1: Check loop conditions for index errors

   The first loop uses i <= str.length, which accesses str[str.length] (undefined), causing an error.

2. Step 2: Correct loop condition to i < str.length

   Changing to i < str.length prevents out-of-bounds access and correctly counts characters.

3. Final Answer:

   The first loop uses <= instead of < causing undefined access -> Option C

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Use < not <= for string index loops to avoid undefined [OK]

Common Mistakes:

• Using <= causes out-of-range errors
• Ignoring loop boundary conditions
• Misunderstanding hash initialization

5. Given the string 'aabbccddeeffg', which modification to the code below will correctly return the first non repeating character?

function firstNonRepeatingChar(str) {
  const hash = {};
  for (const ch of str) {
    hash[ch] = (hash[ch] || 0) + 1;
  }
  for (const ch of str) {
    if (hash[ch] === 1) return ch;
  }
  return '_';
}

Options:
A) Change return '_' to return null
B) Add a check to ignore spaces in the string
C) Modify the function to return '_' if no unique character exists
D) Change the hash to store boolean instead of counts

hard

A. Change return '_' to return null

B. Add a check to ignore spaces in the string

C. Modify the function to return '_' if no unique character exists

D. Change the hash to store boolean instead of counts

Solution

1. Step 1: Analyze the string and current function behavior

   String 'aabbccddeeffg' has all characters repeated except 'g' which appears once.

2. Step 2: Confirm function returns '_' if no unique char

   The function already returns '_' if no unique character is found, which is correct behavior.

3. Step 3: Understand why changing return '_' to return null is better

   Changing return '_' to return null clearly indicates no unique character found, which is a better practice than returning a character that might be confused as valid.

4. Final Answer:

   Change return '_' to return null -> Option A

5. Quick Check:

   Return null when no unique char found is clearer [OK]

Hint: Return null to indicate no unique character found [OK]

Common Mistakes:

• Returning '_' which can be confused as a valid character
• Ignoring spaces when not needed
• Using boolean instead of counts loses frequency info