Why First Non Repeating Character Using Hash in DSA Javascript?

The Big Idea

Discover how a simple hash can save you from endless counting and frustration!

The Scenario

Imagine you have a long list of names, and you want to find the first name that appears only once. Doing this by checking each name one by one and counting how many times it appears can take a lot of time and effort.

The Problem

Manually checking each character or name means going back and forth multiple times. This is slow and easy to make mistakes, especially if the list is very long or has many repeated items.

The Solution

Using a hash (like a JavaScript object) lets you count how many times each character appears in just one pass. Then, you can quickly find the first character that only appears once without checking everything again and again.

Before vs After

✗ Before

function firstNonRepeatingChar(str) {
  for (let i = 0; i < str.length; i++) {
    let count = 0;
    for (let j = 0; j < str.length; j++) {
      if (str[i] === str[j]) count++;
    }
    if (count === 1) return str[i];
  }
  return null;
}

✓ After

function firstNonRepeatingChar(str) {
  const charCount = {};
  for (const char of str) {
    charCount[char] = (charCount[char] || 0) + 1;
  }
  for (const char of str) {
    if (charCount[char] === 1) return char;
  }
  return null;
}

What It Enables

This method makes it easy and fast to find unique items in any list or string, even if it's very long.

Real Life Example

Finding the first unique letter in a username to create a short, easy-to-remember nickname.

Key Takeaways

Manual counting is slow and error-prone.

Hash maps let us count all characters quickly.

We can then find the first unique character in one more quick pass.

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