Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: First Non-repeating Character (easy)

Problem Statement

Given a string, identify the position of the first character that appears only once in the string. If no such character exists, return -1.

Examples

  1. Example 1:

    • Input: "apple"
    • Expected Output: 0
    • Justification: The first character 'a' appears only once in the string and is the first character.

  2. Example 2:

    • Input: "abcab"
    • Expected Output: 2
    • Justification: The first character that appears only once is 'c' and its position is 2.

  3. Example 3:

    • Input: "abab"
    • Expected Output: -1

.....

.....

.....

Like the course? Get enrolled and start learning!
Skyler Liang

Skyler Liang

· 2 years ago

Should space complexity be O(n)?

Show 2 replies
M

mariana.lopez.jaimez

· 2 years ago

In Python, we could take advantage of the Counter() class from the 'collections' library to get the frequency of each character instead of doing it manually. Any tips for improving the following candidate solution would be great:

from collections import Counter

class Solution:
    def firstUniqChar(self, s: str) -> int:
        characters_count = Counter(s)

        for index, character in enumerate(s):
            if characters_count[character] == 1:
                return index
        
        return -1
Sujay

Sujay

· a year ago

  1. We need to iterate through the entire string at least once to count the occurrences of each character. This step alone requires O(n) time, where n is the length of the string.
  2. In the worst case, we might have a string with n-1 repeating characters and a unique character at the end. This means we would need to scan through almost the entire string again to find that unique character