algoadvance

Leetcode 387. First Unique Character in a String

Problem Statement

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

Clarifying Questions

1. Input Constraints:
   • What is the length range of the string s?
   • Can the string contain any special characters or whitespaces?

   Assumption: The string will have a length ranging from 1 to (10^5), and it will contain only lowercase English letters.

2. Output Constraints:
   • Do you require the first unique character to be returned, or just its index?

   The problem specifies to return the index of the first unique character.

Strategy

1. Count Characters: Traverse the string once to count the frequency of each character using an array.
2. Identify First Unique Character: Traverse the string a second time to find the first character with a frequency of 1.

Code

#include <iostream>
#include <string>
#include <vector>

int firstUniqChar(std::string s) {
    std::vector<int> count(26, 0);
    
    // Count the frequency of each character in the string
    for (char ch : s) {
        count[ch - 'a']++;
    }
    
    // Find the first character with a frequency of 1
    for (int i = 0; i < s.length(); ++i) {
        if (count[s[i] - 'a'] == 1) {
            return i;
        }
    }
    
    return -1; // No unique character found
}

int main() {
    std::string s = "leetcode";
    int result = firstUniqChar(s);
    std::cout << "Index of first unique character: " << result << std::endl;

    return 0;
}

Time Complexity

• Time Complexity: (O(n))
  • The first pass over the string to count characters is (O(n)).
  • The second pass to determine the first unique character is (O(n)).
• Space Complexity: (O(1))
  • We are using a fixed-size array of size 26 to store the counts of each character, which is independent of the input size.

This approach ensures that we efficiently find the index of the first unique character in linear time using a simple array for constant time character frequency lookup.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?