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)