Teaching Kids Programming – First Unique Character in a String

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s, return the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1:
Input: s = “leetcode”
Output: 0

Example 2:
Input: s = “loveleetcode”
Output: 2

Example 3:
Input: s = “aabb”
Output: -1

Constraints:
1 <= s.length <= 10^5
s consists of only lowercase English letters.

Python Program to Get First Unique Character

Bruteforce may work: checking each character to see if it is unique – this requires O(N^2) time but O(1) space.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        n = len(s)
        for i in range(n):
            unique = True
            for j in range(n):
                if i != j and s[i] == s[j]:
                    unique = False
                    break
            if unique:
                return i
        return -1

We can use a Counter (O(N) space) to count the character frequencies, and iterate over the string again using enumerate function. And return the first index of the unique character.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        a = Counter(s)
        for i, j in enumerate(s):
            if a[j] == 1:
                return i
        return -1

The time and space complexity is O(N) – where N is the number of the characters in the given string. If the input string is only lowercase characters, the space complexity is O(1) – as we can also use a static array of size 26 to count the number of appearances for lowercases only.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        a = [0] * 26
        for i in s:
            a[ord(i) - 97] += 1
        for i, j in enumerate(s):
            if a[ord(j) - 97] == 1:
                return i
        return -1

ord function gets the ASCII code of a character.

–EOF (The Ultimate Computing & Technology Blog) —