LeetCode 387: First Unique Character in a String Solution in Python – A Step-by-Step Guide

What Is LeetCode 387: First Unique Character in a String?

LeetCode 387: First Unique Character in a String provides a string, and your task is to return the index of the first character that appears exactly once in the string (0-based index), or -1 if no such character exists. It’s a problem that tests your ability to count frequencies and track order efficiently!

Problem Statement

• Input:
• s: String of lowercase letters.
• Output: Integer - Index of the first unique character, or -1 if none.
• Rules:
• Return 0-based index of the first character with frequency 1.
• Case-sensitive (lowercase only per constraint).

Constraints

• 1 <= s.length <= 10⁵
• s contains only lowercase English letters.

Examples

• Input: s = "leetcode"
• Output: 0
• 'l' (index 0) appears once, first unique.
• Input: s = "loveleetcode"
• Output: 2
• 'v' (index 2) is the first unique character.
• Input: s = "aabb"
• Output: -1
• No character appears once.

These show the unique hunt—let’s solve it!

Understanding the Problem: Finding the First Unique Character

To tackle LeetCode 387 in Python, we need to: 1. Identify characters in the string that appear exactly once. 2. Return the index of the first such character (0-based). 3. Return -1 if no unique character exists.

A naive approach might check each character against the rest, but that’s O(n²). We’ll use:

• Best Solution: Hash map—O(n) time, O(1) space (fixed alphabet)—fast and optimal.
• Alternative Solution: List and set—O(n) time, O(n) space—intuitive but less space-efficient.

Let’s find it with the best solution!

Best Solution: Hash Map

Why This Is the Best Solution

The hash map approach runs in O(n) time with O(1) space (26 lowercase letters) by counting character frequencies in one pass, then finding the first character with a count of 1 in a second pass. It’s the most efficient—leveraging a fixed alphabet for constant space and avoiding unnecessary data structures!

How It Works

Think of it like a character tally:

• Hash Map: Count frequency of each character in the string.
• Scan: Iterate string again, return index of first char with count 1.
• Result: Index or -1 if no unique char found.

It’s like counting votes and picking the first solo winner!

Step-by-Step Example

For s = "leetcode":

• Count:
• Map = {'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}.
• Scan:
• 'l' (0): count=1, return 0.
• Result: 0.

For s = "loveleetcode":

• Count:
• Map = {'l': 2, 'o': 2, 'v': 1, 'e': 4, 't': 1, 'c': 1, 'd': 1}.
• Scan:
• 'l' (0): 2, skip.
• 'o' (1): 2, skip.
• 'v' (2): 1, return 2.
• Result: 2.

For s = "aabb":

• Count:
• Map = {'a': 2, 'b': 2}.
• Scan: No count=1, return -1.
• Result: -1.

Code with Explanation

Here’s the Python code using a hash map:

Copy codeclass Solution:
    def firstUniqChar(self, s: str) -> int:
        # Hash map for character frequencies (26 lowercase letters)
        char_count = {}

        # Count frequencies in one pass
        for char in s:
            char_count[char] = char_count.get(char, 0) + 1

        # Find first character with count 1
        for i, char in enumerate(s):
            if char_count[char] == 1:
                return i

        return -1

Explanation

• Line 4: char_count: Dictionary for character frequencies.
• Lines 6-7: Count each character’s frequency—O(n).
• Lines 9-12: Scan string, return index of first char with count 1—O(n).
• Line 14: Return -1 if no unique char—O(1).
• Time: O(n)—two linear passes.
• Space: O(1)—fixed 26-letter alphabet.

This is like a frequency scanner—quick and precise!

Alternative Solution: List and Set

Why an Alternative Approach?

The list and set solution also runs in O(n) time but uses O(n) space by storing all characters in a list and tracking duplicates in a set, then finding the first non-duplicate. It’s less space-efficient—great for understanding an order-preserving approach, though it’s overkill compared to the hash map’s simplicity!

How It Works

• List: Store characters with indices (or use string directly).
• Set: Track duplicates.
• Scan: Mark duplicates, find first non-duplicate.
• Result: Index or -1.

Step-by-Step Example

For s = "leetcode":

• List: ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e'].
• Set:
• Pass 1: Seen = {'l'}.
• 'e': Seen = {'l', 'e'}.
• 'e': Dups = {'e'}, Seen = {'l', 'e'}.
• 't': Seen = {'l', 'e', 't'}.
• ... Dups = {'e'}.
• Scan:
• 'l': Not in Dups, return 0.
• Result: 0.

For s = "aabb":

• Dups: {'a', 'b'}.
• Scan: All in Dups, return -1.

Code with Explanation

Copy codeclass Solution:
    def firstUniqChar(self, s: str) -> int:
        # Set for duplicates and seen characters
        seen = set()
        dups = set()

        # Identify duplicates
        for char in s:
            if char in seen:
                dups.add(char)
            seen.add(char)

        # Find first non-duplicate
        for i, char in enumerate(s):
            if char not in dups:
                return i

        return -1

Explanation

• Lines 4-5: seen: All chars seen, dups: Duplicates.
• Lines 7-10: Mark duplicates—O(n).
• Lines 12-15: Find first char not in dups—O(n).
• Line 17: Return -1 if none—O(1).
• Time: O(n)—two passes.
• Space: O(n)—sets grow with unique chars.

It’s a duplicate marker—works but uses more space!

Comparing the Two Solutions

• Hash Map (Best):
• Time: O(n)—linear.
• Space: O(1)—fixed alphabet.
• Pros: Fast, minimal space.
• Cons: Two passes.
• List and Set (Alternative):
• Time: O(n)—linear.
• Space: O(n)—sets.
• Pros: Clear duplicate logic.
• Cons: More space, less elegant.

Hash map wins for efficiency and space!

Additional Examples and Edge Cases

• s="a": Both return 0.
• s="aa": Both return -1.
• Long string: Hash map scales better in space.

Both work, hash map is optimal.

Complexity Breakdown

• Hash Map:
• Time: O(n).
• Space: O(1).
• List and Set:
• Time: O(n).
• Space: O(n).

Hash map excels for space efficiency.

Key Takeaways

• Hash Map: Count and scan—fast and lean!
• List and Set: Mark and check—clear but heavy!
• Uniqueness: Frequency drives solutions.
• Python Tip: Dicts rock—see [Python Basics](/python/basics).

Final Thoughts: Spot That Char

LeetCode 387: First Unique Character in a String in Python is a frequency challenge. Hash map is the efficiency champ, while list and set offers a straightforward alternative. Want more? Try LeetCode 242: Valid Anagram or LeetCode 383: Ransom Note. Ready to hunt? Visit Solve LeetCode 387 on LeetCode and find that unique char today!