First Non Repeating Character Using Hash in DSA Python - Build from Scratch

First Non Repeating Character Using Hash

📖 Scenario: Imagine you are building a simple text analyzer tool. One of the features is to find the first character in a sentence that does not repeat. This helps highlight unique characters for fun word games or puzzles.

🎯 Goal: Build a program that finds the first non-repeating character in a given string using a hash (dictionary) to count character occurrences.

📋 What You'll Learn

Create a string variable with a specific sentence

Create a dictionary to count characters

Use a loop to fill the dictionary with character counts

Use another loop to find the first character with count 1

Print the first non-repeating character or a message if none found

💡 Why This Matters

🌍 Real World

Finding unique characters is useful in text analysis, cryptography, and word games.

💼 Career

Understanding how to count and analyze data using dictionaries is a key skill in programming and data processing jobs.

1

Create the input string

Create a string variable called text and set it to the exact value 'swiss'.

DSA Python

# Create the string variable 'text' with value 'swiss'
# Your code here

Hint

Use single quotes around the word swiss.

2

Create a dictionary to count characters

Create an empty dictionary called char_count to store character counts.

DSA Python

text = 'swiss'
# Create an empty dictionary called 'char_count'
# Your code here

Hint

Use curly braces {} to create an empty dictionary.

3

Count characters using a loop

Use a for loop with variable char to iterate over text. Inside the loop, update char_count[char] to count how many times each character appears.

DSA Python

text = 'swiss'
char_count = {}
# Use a for loop to count characters in 'text'
# Your code here

Hint

Check if char is already a key in char_count. If yes, add 1; if no, set to 1.

4

Find and print the first non-repeating character

Use a for loop with variable char to iterate over text. Inside the loop, check if char_count[char] is 1. If yes, print char and break the loop. If no such character is found, print 'No non-repeating character found'.

DSA Python

text = 'swiss'
char_count = {}
for char in text:
    if char in char_count:
        char_count[char] += 1
    else:
        char_count[char] = 1

# Find and print the first non-repeating character
# Your code here

Hint

Use a for-else structure to print the character or a message if none found.

Practice

1. What does the "First Non Repeating Character Using Hash" algorithm primarily do?

easy

A. Finds the first character in a string that appears only once

B. Counts the total number of characters in a string

C. Sorts characters of a string alphabetically

D. Reverses the string

Solution

1. Step 1: Understand the problem goal

   The algorithm aims to find the first character in the string that does not repeat anywhere else.

2. Step 2: Identify the main operation

   It uses a hash (dictionary) to count occurrences and then finds the first character with count 1.

3. Final Answer:

   Finds the first character in a string that appears only once -> Option A

4. Quick Check:

   First unique character = first non repeating character [OK]

Hint: Look for the first character with count one in the hash [OK]

Common Mistakes:

• Thinking it counts total characters instead of unique
• Confusing sorting with finding unique characters
• Assuming it reverses the string

2. Which of the following Python code snippets correctly initializes a hash (dictionary) to count characters in a string s?

easy

A. counts = []; for ch in s: counts[ch] += 1

B. counts = {}; for ch in s: counts[ch] = counts.get(ch, 0) + 1

C. counts = set(); for ch in s: counts.add(ch)

D. counts = 0; for ch in s: counts += 1

Solution

1. Step 1: Check dictionary initialization and update

   counts = {}; for ch in s: counts[ch] = counts.get(ch, 0) + 1 correctly creates an empty dictionary and updates counts using get with default 0.

2. Step 2: Analyze other options

   counts = []; for ch in s: counts[ch] += 1 uses a list which cannot be indexed by characters; counts = set(); for ch in s: counts.add(ch) uses a set which only stores unique items without counts; counts = 0; for ch in s: counts += 1 uses an integer which cannot store counts per character.

3. Final Answer:

   counts = {}; for ch in s: counts[ch] = counts.get(ch, 0) + 1 -> Option B

4. Quick Check:

   Dictionary with get method counts chars correctly [OK]

Hint: Use dict.get(key, 0) to count characters safely [OK]

Common Mistakes:

• Using list instead of dictionary for counts
• Using set which does not count duplicates
• Trying to increment integer without keys

3. What is the output of the following code?

def first_non_repeating(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in s:
        if counts[ch] == 1:
            return ch
    return '_'

print(first_non_repeating('swiss'))

medium

A. s

B. _

C. i

D. w

Solution

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

   Counts: s=3, w=1, i=1

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

   Order: s (3), w (1) -> first non repeating is 'w'

3. Final Answer:

   w -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Returning first unique char incorrectly as 's'
• Confusing 'i' as first unique instead of 'w'
• Returning '_' when unique char exists

4. The following code is intended to find the first non repeating character but has a bug. What is the bug?

def first_non_repeating_bug(s):
    counts = {}
    for ch in s:
        counts[ch] += 1
    for ch in s:
        if counts[ch] == 1:
            return ch
    return '_'

medium

A. The for loop should iterate over counts.keys() instead of s

B. The return '_' statement is unreachable

C. counts dictionary is not initialized with default values before increment

D. The function does not return anything

Solution

1. Step 1: Analyze counts dictionary usage

   The code tries to increment counts[ch] without initializing counts[ch], causing KeyError.

2. Step 2: Identify missing initialization

   Must initialize counts[ch] to 0 before increment or use counts.get(ch, 0) + 1.

3. Final Answer:

   counts dictionary is not initialized with default values before increment -> Option C

4. Quick Check:

   Missing initialization causes KeyError [OK]

Hint: Initialize counts[ch] before increment or use get() [OK]

Common Mistakes:

• Assuming return '_' is unreachable
• Thinking loop over s is wrong
• Believing function returns nothing

5. Given the string s = 'aabbccddeeffg', which character will the first non repeating character algorithm return?
Note: The algorithm uses a hash to count characters and returns the first character with count 1 or '_' if none.

medium

A. g

B. a

C. _

D. f

Solution

1. Step 1: Count occurrences of each character in 'aabbccddeeffg'

   a=2, b=2, c=2, d=2, e=2, f=2, g=1

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

   All characters except 'g' repeat twice; 'g' appears once at the end.

3. Final Answer:

   g -> Option A

4. Quick Check:

   Only 'g' is unique in the string [OK]

Hint: Check counts; last unique char is first non repeating here [OK]

Common Mistakes:

• Choosing 'a' or 'f' which repeat twice
• Choosing '_' when unique char exists
• Ignoring order of characters