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 ・ Feb 6, 2021 ・

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

1. Leetcode 442: Find All Duplicates in an Array
2. Leetcode 1429: First Unique Number

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

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

LeetCode Simplified