Grokking the Engineering Manager Coding Interview

0% completed

​

First Non-repeating Character (easy)

Problem Statement

Try it yourself

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
    • Justification: There is no character in the string that appears only once.

Constraints:

  • 1 <= s.length <= 10<sup>5</sup>
  • s consists of only lowercase English letters.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
Mark as Completed
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

· 2 years 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

On This Page

Problem Statement

Try it yourself