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

## Solve Leetcode Problems and Get Offers From Your Dream Companies | by Nil Madhab | LeetCode Simplified | Medium

### Nil Madhab ・ ・
Medium

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

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

The C++ code is also given below.

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

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

**Similar Problems**

The code for this problem can be found in the following repository.

**Thank You for reading and Follow this publication for more Leetcode problems!😃**

## Top comments (0)