Leetcode 387. First Unique Character in a String

In this series, I am going to solve Leetcode medium problems live with my friends, which you can see on our youtube channel, Today we will do Problem Leetcode 387. First Unique Character in a String

A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.

Motivation to learn algorithms

Problem Statement

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

Examples:

s = "leetcode"
return 0.s = "loveleetcode"
return 2.

Note: You may assume the string contains only lowercase English letters.

Youtube Discussion

Leetcode 387. First Unique Character in a String

Solution

According to the problem, we have to return the index of the first non-repeating character.

Naive Solution

Let’s talk about the naive approach to the problem. We can choose a character from the string at index i and check for its occurrence in the left substring (0 to i-1) and the right substring (i+1 to the end of the string).

If that character does not appear in any of those we return that index i . This will give us a time complexity of O(n^2) .

Optimized solution

Now let’s try to improve it.

When dealing with problems involving the frequency of characters, we should try to use a Hash Table.

For this problem, we have to count the occurrence of each character and return the first character’s index whose count is 1. Therefore, we can first store the occurrence of all characters and then check for the character which occurs just once.

public class LC387 {
        public int firstUniqChar(String s) {
            //hashmap to store character frequency
            HashMap<Character, Integer> hashMap = new HashMap<>();

            for (int i = 0; i < s.length(); i++) {

                char c = s.charAt(i);

                //count the occurance of each character
                if (hashMap.containsKey(c))
                    hashMap.put(c, hashMap.get(c) + 1);
                else
                    hashMap.put(c, 1);

            }


            //Iterate through the string again.
            for (int i = 0; i < s.length(); i++) {


                char c = s.charAt(i);
                //If a characters occurance is 1 then we return the index
                if (hashMap.get(c) == 1)
                    return i;


            }

            //If no character has an occurance of 1 we return -1
            return -1;

        }
}

The C++ code is also given below.

class LC387 {
public:
int firstUniqChar(string s) {
        map<char, int> m ;

        for(int i =0 ; i<s.length();i++){
            m[s[i]]++;
        }
         for(int i =0 ; i<s.length();i++){
         if(m[s[i]]==1)
             return i;
        }
        return -1;
    }

}

Time Complexity: O(n), n is the length of the string

Space Complexity: O(1), at max the hashmap will have 26 keys.