First Unique Character in String

Find the first non-repeating character in a string and return its index.

Language Selection

Choose your preferred programming language

Showing: Python

First Unique Character in String

Problem Statement

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

Examples

Example 1:

Input: s = "leetcode"
Output: 0
Explanation: The character 'l' at index 0 is the first non-repeating character.

Example 2:

Input: s = "loveleetcode"
Output: 2
Explanation: The character 'v' at index 2 is the first non-repeating character.

Example 3:

Input: s = "aabb"
Output: -1
Explanation: All characters repeat, so return -1.

Constraints

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

Approach 1: Two-Pass Hash Map

Algorithm

Use a hash map to count character frequencies, then iterate through the string to find the first character with frequency 1.

Steps:

Count frequency of each character
Iterate through string to find first character with frequency 1
Return its index or -1 if not found

Implementation

Python:

def first_uniq_char(s):
    """
    Find first unique character using hash map
    Time: O(n)
    Space: O(1) - at most 26 characters
    """
    # Count character frequencies
    char_count = {}
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Find first character with frequency 1
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i
    
    return -1

Java:

class Solution {
    /**
     * Find first unique character using hash map
     * Time: O(n)
     * Space: O(1) - at most 26 characters
     */
    public int firstUniqChar(String s) {
        // Count character frequencies
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        // Find first character with frequency 1
        for (int i = 0; i < s.length(); i++) {
            if (charCount.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

Go:

// firstUniqChar - Find first unique character using hash map
// Time: O(n)
// Space: O(1) - at most 26 characters
func firstUniqChar(s string) int {
    // Count character frequencies
    charCount := make(map[rune]int)
    for _, char := range s {
        charCount[char]++
    }
    
    // Find first character with frequency 1
    for i, char := range s {
        if charCount[char] == 1 {
            return i
        }
    }
    
    return -1
}

JavaScript:

/**
 * Find first unique character using hash map
 * Time: O(n)
 * Space: O(1) - at most 26 characters
 */
function firstUniqChar(s) {
    // Count character frequencies
    const charCount = {};
    for (const char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    
    // Find first character with frequency 1
    for (let i = 0; i < s.length; i++) {
        if (charCount[s[i]] === 1) {
            return i;
        }
    }
    
    return -1;
}

C#:

public class Solution {
    /// <summary>
    /// Find first unique character using hash map
    /// Time: O(n)
    /// Space: O(1) - at most 26 characters
    /// </summary>
    public int FirstUniqChar(string s) {
        // Count character frequencies
        var charCount = new Dictionary<char, int>();
        foreach (char c in s) {
            charCount[c] = charCount.GetValueOrDefault(c, 0) + 1;
        }
        
        // Find first character with frequency 1
        for (int i = 0; i < s.Length; i++) {
            if (charCount[s[i]] == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(1) since we have at most 26 characters

Approach 2: Array for Character Counting

Algorithm

Use an array of size 26 to count character frequencies instead of a hash map, since we only have lowercase English letters.

Implementation

Python:

def first_uniq_char_array(s):
    """
    Find first unique character using array
    Time: O(n)
    Space: O(1) - fixed size array of 26
    """
    # Count character frequencies using array
    char_count = [0] * 26
    for char in s:
        char_count[ord(char) - ord('a')] += 1
    
    # Find first character with frequency 1
    for i, char in enumerate(s):
        if char_count[ord(char) - ord('a')] == 1:
            return i
    
    return -1

Java:

class Solution {
    /**
     * Find first unique character using array
     * Time: O(n)
     * Space: O(1) - fixed size array of 26
     */
    public int firstUniqCharArray(String s) {
        // Count character frequencies using array
        int[] charCount = new int[26];
        for (char c : s.toCharArray()) {
            charCount[c - 'a']++;
        }
        
        // Find first character with frequency 1
        for (int i = 0; i < s.length(); i++) {
            if (charCount[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

Go:

// firstUniqCharArray - Find first unique character using array
// Time: O(n)
// Space: O(1) - fixed size array of 26
func firstUniqCharArray(s string) int {
    // Count character frequencies using array
    charCount := make([]int, 26)
    for _, char := range s {
        charCount[char-'a']++
    }
    
    // Find first character with frequency 1
    for i, char := range s {
        if charCount[char-'a'] == 1 {
            return i
        }
    }
    
    return -1
}

JavaScript:

/**
 * Find first unique character using array
 * Time: O(n)
 * Space: O(1) - fixed size array of 26
 */
function firstUniqCharArray(s) {
    // Count character frequencies using array
    const charCount = new Array(26).fill(0);
    for (const char of s) {
        charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // Find first character with frequency 1
    for (let i = 0; i < s.length; i++) {
        if (charCount[s[i].charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
            return i;
        }
    }
    
    return -1;
}

C#:

public class Solution {
    /// <summary>
    /// Find first unique character using array
    /// Time: O(n)
    /// Space: O(1) - fixed size array of 26
    /// </summary>
    public int FirstUniqCharArray(string s) {
        // Count character frequencies using array
        int[] charCount = new int[26];
        foreach (char c in s) {
            charCount[c - 'a']++;
        }
        
        // Find first character with frequency 1
        for (int i = 0; i < s.Length; i++) {
            if (charCount[s[i] - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(1) for the fixed-size array

Key Insights

Two-Pass Approach: First pass counts frequencies, second pass finds first unique
Space Optimization: Use array instead of hash map for better performance
Character Mapping: Map characters to array indices using ASCII values
Early Termination: Can stop as soon as first unique character is found

Edge Cases

Single character: String with one character
All unique: Each character appears once
All repeated: Every character appears multiple times
Empty string: Handle empty input (though constraints say length >= 1)
Two characters: Minimum case with two characters

Test Cases

# Test cases
assert first_uniq_char("leetcode") == 0
assert first_uniq_char("loveleetcode") == 2
assert first_uniq_char("aabb") == -1
assert first_uniq_char("a") == 0
assert first_uniq_char("ab") == 0
assert first_uniq_char("aa") == -1
assert first_uniq_char("abcdef") == 0

Follow-up Questions

First Unique Character in Stream: Handle characters arriving one by one
Kth Unique Character: Find the kth non-repeating character
Unique Characters Count: Count total number of unique characters
Remove Duplicates: Remove all duplicate characters from string
Longest Substring with Unique Characters: Find longest substring with all unique characters

Common Mistakes

Index confusion: Returning character instead of index
Case sensitivity: Not handling case differences properly
Empty string: Not handling edge case of empty string
Character vs index: Confusing character value with its index
Frequency counting: Incorrect frequency counting logic

Interview Tips

Clarify requirements: Ask about case sensitivity and character set
Start simple: Begin with hash map approach, then optimize
Discuss trade-offs: Hash map vs array for character counting
Handle edge cases: Always consider single character and all repeated cases
Optimize space: Mention array optimization for lowercase letters only

Variations

Case-insensitive: Ignore case differences
Extended ASCII: Handle extended character set
Unicode: Support Unicode characters
Case-sensitive: Distinguish between uppercase and lowercase
Custom alphabet: Handle custom character sets