First Unique Character In A String

First Unique Character in a String

Difficulty: Easy

Asked in: Amazon, Microsoft

Understanding the problem

Problem description Given a string S, write a program to find the first non-repeating character in it and return its index.

Problem Note

If a non-repeating character doesn’t exist, return -1.
You may assume the string contains only lowercase letters.

Example 1

Input: S = "afteracademy"
Output: 1

Example 2

Input: S = "mindorks"
Output: 0

Example 3

Input: S = "abacdcd"
Output: -1

You should try to solve this problem here.

Solutions

We will be discussing two different approaches to solve this problem

Brute Force Approach — Compare each pair of characters and find the first character which is not repeated.
Using a hash map — Use a hash map to store the frequency of each character.

1. Brute Force Approach

To find the first non-repeating character, we may look for every pair of characters in the string. The first occurring character which does not have any pair will be the answer.

In case of no such characters, return -1.

Pseudo Code

int firstUniqueChar(string s) {
    len = s.length()
    for(i = 0 to i < len){
        bool found = true
        for(j = i+1 to j < len){
            if(s[i] == s[j]){
                found = false
                break
            }
        }
        if(found == true){
            return i
        }
    }
    return -1
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(1)

Critical Ideas to Think

Why we are using the found variable in the pseudo code?
If we remove the break statement from the code, will the code work?
Can you optimize the code to improve time complexity?

2. Using Hash Map

If you have read about hashmaps then, you would know that the lookup time of a key is constant. In this problem, we could use the hashmap to store the frequency of each character of the string and that could be done in a single pass of the string.

In another pass of the string, we may look for the first character with value in the map equal to 1.

Solution Step

create one frequency map

for each character c in the string, do
if c is not in frequency, then insert it into frequency, and put value 1
otherwise, increase the count in frequency

2. Scan the string and check if the value of the ith character in the map is 1 then return i. 3. Return -1, in case of the value of each character in the map, is greater than 1

Pseudo Code

int firstUniqChar(String s) {
    Create a Hashmap freq
    n = s.length()
    // build hash map : character and how often it appears
    for (int i = 0 to i < n) {
        c = s[i]
        freq[c] = freq[c] + 1
    }   
    // find the index
    for (int i = 0 to i < n) {
        if (freq[s[i]] == 1) 
            return i
    }
    return -1
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Critical Ideas to Think

If we replace the freq map with an array of size 26 and use each index of the array as the (ASCII of that character) — 97, will that approach work? (97 is the ASCII of 'a')