387. First Unique Character in a String

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

Given a string s, find 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
Explanation: The first non-repeating character is 'l' with index 0.

Example 2:

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

Example 3:

Input: s = "aabb"
Output: -1
Explanation: There is no non-repeating character, so return -1.

Constraints:

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

Solution

Python Solution

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Count character frequencies
        char_count = {}
        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

Time Complexity: O(n)

Where n is the length of the string. We need two passes through the string.

Space Complexity: O(1)

Since we only store lowercase English letters (26 characters max).

Java Solution

class Solution {
    public int firstUniqChar(String s) {
        // Count character frequencies
        int[] charCount = new int[26];
        for (char c : s.toCharArray()) {
            charCount[c - 'a']++;
        }
        
        // Find first character with count 1
        for (int i = 0; i < s.length(); i++) {
            if (charCount[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

Time Complexity: O(n)

Where n is the length of the string. We need two passes through the string.

Space Complexity: O(1)

Since we only use a fixed-size array of 26 characters.

C++ Solution

class Solution {
public:
    int firstUniqChar(string s) {
        // Count character frequencies
        vector charCount(26, 0);
        for (char c : s) {
            charCount[c - 'a']++;
        }
        
        // Find first character with count 1
        for (int i = 0; i < s.length(); i++) {
            if (charCount[s[i] - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
};

Time Complexity: O(n)

Where n is the length of the string. We need two passes through the string.

Space Complexity: O(1)

Since we only use a fixed-size vector of 26 characters.

JavaScript Solution

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    // Count character frequencies
    const charCount = new Map();
    for (const char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    // Find first character with count 1
    for (let i = 0; i < s.length; i++) {
        if (charCount.get(s[i]) === 1) {
            return i;
        }
    }
    
    return -1;
};

Time Complexity: O(n)

Where n is the length of the string. We need two passes through the string.

Space Complexity: O(1)

Since we only store lowercase English letters (26 characters max).

C# Solution

public class Solution {
    public int FirstUniqChar(string s) {
        // Count character frequencies
        int[] charCount = new int[26];
        foreach (char c in s) {
            charCount[c - 'a']++;
        }
        
        // Find first character with count 1
        for (int i = 0; i < s.Length; i++) {
            if (charCount[s[i] - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

Time Complexity: O(n)

Where n is the length of the string. We need two passes through the string.

Space Complexity: O(1)

Since we only use a fixed-size array of 26 characters.

Approach Explanation

The solution uses a two-pass approach with character counting:

Key Insights:
- Count frequencies first
- Maintain character order
- Early termination
- Constant space possible
Algorithm Steps:
- Count all characters
- Find first unique
- Check frequencies
- Return position

Implementation Details:

Array vs HashMap choice
Character indexing
Frequency tracking
Index maintenance

Optimization Insights:

Fixed-size array
Single pass not possible
Space optimization
Early returns

Edge Cases:

Empty string
All repeating
Single character
No unique character