We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

First Unique Character in a String

Number: 387

Difficulty: Easy

Paid? No

Companies: Goldman Sachs, Bloomberg, Amazon, Google, Apple, Microsoft, Yandex, Meta, EPAM Systems, ServiceNow, Yahoo, Adobe, Oracle, PayPal, Nvidia, Ozon

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.

Key Insights

  • Use a hash table (or fixed-size array) to count the frequency of each character in the string.
  • Iterate over the string a second time to find the first character with a frequency of one.
  • The solution handles the case where no unique character exists by returning -1.

Space and Time Complexity

Time Complexity: O(n) - two passes over the string. Space Complexity: O(1) - only 26 lowercase letters are stored, which is a constant space.

Solution

This solution leverages a frequency counting approach with a hash table (or fixed-size array for the 26 lowercase letters). In the first pass, the frequency of each character in the string is recorded. In the second pass, the string is iterated again to locate the first character with a count of one. If found, its index is returned; if not, -1 is returned. This strategy provides an efficient way to solve the problem with just two passes over the input string.

Code Solutions

Python:

JavaScript:

C++:

Java:

def firstUniqChar(s):
    # Create a frequency dictionary to count occurrences of each character
    char_count = {}
    # First pass: count every character in the string
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1
    # Second pass: find the first character that occurs exactly once
    for index, char in enumerate(s):
        if char_count[char] == 1:
            return index
    # Return -1 if no unique character is found
    return -1

# Example usage:
print(firstUniqChar("leetcode"))    # Expected output: 0
print(firstUniqChar("loveleetcode")) # Expected output: 2
← Back to All Questions