# Leetcode 387. First Unique Character in a String

Nilmadhab

2 years ago | 3 min read

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.

# 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.

Upvote

Created by

Nilmadhab

Developer @Booking.com | ex: Samsung, OYO | IIT Kharagpur | Entrepreneur, founder of simplecoding.dev | connect me https://twitter.com/Nilmadhabmondal

Post

Upvote

Downvote

Comment

Bookmark

Share

Related Articles