First Unique Character in a String (Leet code-387)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 387. This is a Leet code problem named First Unique Character in a String. We will solve it using python and it is the best space and time-optimized solution.

Question of First Unique Character in a String

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

Explanation

If a character only appears once in the string, it is considered to be non-repeating. Finding the frequency of each character in the string and determining which character has a unit frequency are the next steps in locating such characters. A hash map, which maps characters to their corresponding frequencies and allows us to simultaneously update the frequency of each character we encounter in constant time, is an effective tool for doing this task.

Example

Example 1

Input: s = "leetcode"
Output: 0

Example 2

Input: s = "loveleetcode"
Output: 2

Example 3

Input: s = "aabb"
Output: -1

Constraints

1 <= s.length <= 10⁵
s consists of only lowercase English letters.

Approach to solve First Unique Character in a String

To solve this problem we simply traverse the string once and create two hashmaps. In the first hashmap, we store only the unique characters. In the second hashmap, we store the character when it occurs the first time. The only difference between both the hashmap is that in the first hashmap we will pop the element when it comes again.

Algorithm

This method performs the following steps for a given input array:

Create hashmap variable first_unique to store element when it occurs the first time.
string_elem hashmap to store all visited elements once.
Run for loop to iterate over all elements of a string.
Check if the character is visited once or not.
If not visited then add it in both hashmaps.
Check if the element is in a unique hashmap.
If present then pop it.
End For
If there is a unique element then return its position.
otherwise return -1

Python Code for First Unique Character in a String

class Solution:
    def firstUniqChar(self, s: str) -> int:
        
        
        #hashmap to store element when it occurs first time
        first_unique={}
        #hashmap to store all visited elements once
        string_elem={}
        #in both the hashmap we will use character and position as a key value pair
        
        #iterate through all characters
        for i in range(len(s)):
            #check if character is visited once or not
            if s[i] not in string_elem:
                #if not visited then add it in both hashmap
                first_unique[s[i]] = i
                string_elem[s[i]] = i
            #check if element is in unique hashmap
            elif s[i] in first_unique:
                #if present then remove it
                first_unique.pop(s[i])
                
        #if there is unique element then return its position
        if(len(first_unique)>0):
            res = list(first_unique.keys())[0]
            return first_unique[res]
        #otherwise return -1
        else:
            return -1