LeetCode - First Unique Character in a String

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem no. 387, First Unique Character in a String.

Problem Statement: First Unique Character in a String

Given a string s find the first unique/non-repeating character in it, return its index as result. If it does not exist return -1.

Example

Example 1:

Input: s = "leetcode"
Output: 0
Explanation:
The character 'l' at index 0 is the first character that does not occur at any other index.

Example 2:

Input: s = "loveleetcode"
Output: 2

Example 3:

Input: s = "aabb"
Output: -1

Constraints:

• 1 <= s.length <= 10^5

• s consists of only lowercase English letters.

Solution

If we read through the problem statement, it is mostly obvious what data structure we should be using to solve this problem. Since we are dealing with character count here, hashmap should be the first data structure that should come to our mind.

This problem is labeled as an easy problem on leetcode, and it is indeed an easy one, but it comes with a slight caveat. And if this doesn't strike to you right away, it could prove a bit tricky sometimes. Let's see how we can go about solving this problem using hashmap data structure.

Algorithm

Below is the step by step explanation for this algorithm:

1. As mentioned earlier this algorithm makes use of a hashmap. Initialize a hashmap with a char type key (byte in some languages) and integer type value. Let's call this hashmap freq (short for frequency).

2. After this, we iterate through the given input string s from start to end.

3. In each iteration we increment the current character count by 1 in our hashmap freq.

4. At the end of step 3, we have all the characters in the string s in our hashmap along with the frequency of occurrence of each character.

5. Now, we iterate through the string s one more time and in each iteration we perform either of the below two steps:

   1. If the current character count in freq is equal to one, we have found the first unique character in string s and hence our result. So, we return the current index as result.

   2. If count is not equal to one, it is not a unique character. Therefore we simply continue iterating through the string.

6. If the execution comes out of the second for loop, without returning, it means there are no unique characters in the input string s. Therefore we return -1 as result as mentioned in the problem statement.

Simulation

Below diagram shows a pictorial depiction of the working of this algorithm:

Want to master coding? Looking to learn upskill and crack interviews? We recommend you explore these tailor made courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

C++ Solution

C# Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Complexity Analysis

Time Complexity

First Loop: The first loop iterates through string s from start to end, once. This has a time complexity of O(n), where n is the length of string s.

Second Loop: The second loop iterates through string s until it finds the first unique character. In the worst case if i.e. when a unique character is at the last position in string s or if unique character is not found, then this loop has to iterate till the end. So, the time complexity of this loop is also O(n).

Hashmap Operations: All hashmap operations inside both these loops are constant time operations with time complexity O(1).

Therefore the overall time complexity of this solution is O(n) + O(n) = O(n).

Space Complexity

This solution uses a hashmap freq to store the frequencies of characters in string s. Apart from this we do not use any additional storage for our computation.

In the worst case when all the characters in string s are unique, this algorithm ends up storing the count for all characters in freq. But since we dealing with only lower case english letters (as mentioned in constraints) the space complexity in the worst case is O(26), which in general can be represented as O(1).

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.