Leetcode – First Unique Character in a String Solution in Python

Spread the love

Introduction

One of the classic problems you can find on LeetCode is the “First Unique Character in a String” problem. This article will guide you through understanding this problem and discuss various approaches to solve it using Python.

Problem Statement

Given a string, find the first non-repeating character in it and return its index. If it doesn’t exist, return -1.

Analyzing the Problem

The problem requires us to find the first character in the given string that does not repeat. For example, in the string “leetcode”, the first non-repeating character is ‘l’, so the function should return 0 (the index of ‘l’).

Let’s explore different approaches to solve this problem:

Approach 1: Using a Hash Table

We can use a hash table (or dictionary in Python) to keep track of the frequency of each character in the string. In the first pass, we populate the hash table with the character counts. In the second pass, we check for the first character that has a count of 1 and return its index.

def firstUniqChar(s: str) -> int:
    char_count = {}
    
    # First pass: Count the frequency of each character
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
        
    # Second pass: Find the index of the first unique character
    for index, char in enumerate(s):
        if char_count[char] == 1:
            return index
        
    return -1

This approach has a time complexity of O(N) where N is the length of the string, and a space complexity of O(1) as the hash table stores at most 26 characters (assuming lowercase English letters).

Approach 2: Using Collections Counter

Python has a built-in module called collections which has a Counter class that makes counting the elements in an iterable more concise. We can use the Counter to count the characters and then iterate through the string to find the first unique character.

from collections import Counter

def firstUniqChar(s: str) -> int:
    # Count the frequency of each character
    char_count = Counter(s)
    
    # Find the index of the first unique character
    for index, char in enumerate(s):
        if char_count[char] == 1:
            return index
            
    return -1

This approach is similar to the first approach but uses the Counter class for cleaner code.

Approach 3: Using an OrderedDict

We can further optimize by keeping track of the characters and their indices using an OrderedDict. This allows us to keep the insertion order and find the first unique character in a single pass.

from collections import OrderedDict

def firstUniqChar(s: str) -> int:
    char_indices = OrderedDict()
    
    # Keep track of indices and count of characters
    for index, char in enumerate(s):
        if char in char_indices:
            char_indices[char] = (index, char_indices[char][1] + 1)
        else:
            char_indices[char] = (index, 1)
            
    # Find the first unique character
    for index, count in char_indices.values():
        if count == 1:
            return index
        
    return -1

This approach has the same time complexity of O(N) but may have slightly reduced constants in practice.

Best Practices and Optimization

It is important to note that optimization could be problem-specific. For this problem, using a hash table is a practical and efficient solution. However, the choice between using a basic dictionary, a Counter, or an OrderedDict can depend on readability and slight performance preferences.

Conclusion

In this extensive article, we have explored the “First Unique Character in a String” problem from LeetCode and discussed various approaches to solving it using Python. We have seen how hash tables and data structures provided by the collections module can be used to solve this problem efficiently.

Leave a Reply