First Non Repeating Character Using Hash in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a dictionary to count characters.

DSA Python

count = [1]()

Drag options to blanks, or click blank then click option'

Adict

Blist

Cset

Dtuple

Attempts:

3 left

💡 Hint

Common Mistakes

Using list or set instead of dictionary for counting.

Trying to use tuple which is immutable.

We use dict() to create a dictionary for counting characters.

2fill in blank

medium

Complete the code to increment the count of character c in the dictionary.

DSA Python

count[c] = count.get(c, 0) [1] 1

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using minus or multiplication instead of addition.

Forgetting to handle the default count with get.

We add 1 to the current count to increment the character count.

3fill in blank

hard

Fix the error in the loop to find the first non-repeating character.

DSA Python

for c in s:
    if count[c] == [1]:
        return c

Drag options to blanks, or click blank then click option'

A0

B-1

C2

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for count 0 or 2 instead of 1.

Using negative numbers which don't make sense here.

The first non-repeating character has a count of exactly 1.

4fill in blank

hard

Fill both blanks to complete the function that returns the first non-repeating character or '_' if none.

DSA Python

def first_non_repeating(s):
    count = dict()
    for c in s:
        count[c] = count.get(c, 0) [1] 1
    for c in s:
        if count[c] == [2]:
            return c
    return '_'

Drag options to blanks, or click blank then click option'

A+

B-

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operators for increment.

Checking for count 0 instead of 1.

We increment counts by 1 and check if count equals 1 for non-repeating characters.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that counts characters appearing more than once.

DSA Python

count = [1]( (c, s.count(c)) for c in s if s.count(c) [2] [3] )

Drag options to blanks, or click blank then click option'

Adict

B>

C1

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using list or set instead of dict.

Using less than instead of greater than.

Checking for count equal to 1 instead of greater than 1.

We use dict to create the dictionary, check if count is greater than 1 to find repeating characters.

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