First Unique Character in a String LeetCode Solution

Problem Statement

First Unique Character in a String LeetCode Solution – Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example

Test Case 1:

Input:

s = “leetcode”

Output:

0

Test Case 2:

Input:

s = “aabb”

Output:

-1

Explanation

i) In the first test case, ‘l’ is the first unique character. The index of ‘l’ is 0.

ii) In the second test case, there is no unique character. So we return -1.

Approach:

Main idea short version: Two passes through the input string. In the first pass, we can count the number of times each character appears. In the second pass return the first character in the string that appears exactly once.

Main idea long version: A unique character is a character that appears exactly once. No more, no less. So we can

1. traverse string to keep track number of times each character in the string appears
2. traverse string again to find a character that appears exactly one time, return it’s index
3. return -1 if none no character appeared exactly once

To keep track of the count of each character, we initialize an int[] chrs with size 26. After the first pass, each element at index i will represent the number of times the ith character of the alphabet appears in the string. So, chrs[0] will represent the number of times ‘a’ appears, and chrs[5] will represent the number of times the 5th element of the alphabet, ‘e’, appears. To access the chrs[] element representative of each character, we subtract ‘a’ from that character.

For example, ‘a’ – ‘a’ results in 0 -> Perfectly aligning because ‘a’ is the 0th element in the alphabet
Another example, ‘e’ – ‘a’, results in 5 -> Perfectly aligning because ‘e’ is the 5th element in the alphabet

Then, in the second pass, we simply search for the first element that appeared exactly once. We use the same subtract ‘a’ trick to access the element in chrs[] representative of each character. Finally, if none appeared exactly once we return -1.

Code for First Unique Character in a String

Java Program

class Solution {
    public int firstUniqChar(String s) {
        int len = s.length();
        
        if(len == 0){
            return -1;
        }
        
        int[] arr = new int[26];
        
        for(char c : s.toCharArray()){
            arr[c - 'a']++;
        }
        
        for(int i=0; i<len; i++){
            if(arr[s.charAt(i) - 'a'] == 1){
                return i;
            }
        }
        
        return -1;
    }
}

C++ Program

class Solution {
public:
    int firstUniqChar(string s) {
        map<char, int> G; // Map char to its count in the string
        for (int i{}; i < s.size(); i++) { 
      G[s[i]]++;  // Everytime the character appears in the string, add one to its count
    } 
        for (int i{}; i < s.size(); i++) { // Start traversing the string from the beginning. 
      if (G[s[i]] == 1) return i; // If the count of the char is equal to 1, it is the first distinct character in the list.
    } 
        return -1;
    }
};

Complexity Analysis for First Unique Character in a String LeetCode Solution

Time Complexity: O(n)

Space Complexity: O(1) as we are using constant space.