LeetCode 387: Finding the First Unique Character - Frequency Mapping in Java

Difficulty: Easy

Topics: Hash Table, String, Queue, Counting

Platform: Leetcode

Problem Statement

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

Problem Statement Simplified
Get the index of the first non-repeating character, else return -1.

Mistakes and Learning
Do not blindly loop thorugh.
Do not just delete the duplicates, remove the duplicated character also.

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`

Key Insight

• Remove all the duplicating characters

• Then get the first character

• Get the first character index.

• If no unique then -1.

Algorithm

1. Convert the string to a char array.
2. Intitialize a HashMap to store the character and the repeating counts.
3. Intitialize a for loop
4. Put the character in the HashMap with getOrDefault to check if the character already preset or not, if yes then increment by 1.
5. End for loop
6. Intitialize a for loop
7. Check if the first value is 1 if yes then return the for loop index else continue the for loop
8. End for loop
9. return -1

Algorithm in simple words

First, convert the string to a char array. Then initialize a HashMap so that we can store each character with its repeating counts.
Then initialize a for loop to add each character from character array to HashMap with getOrDefault ( if the value of preseent the increment b 1 else it will be 0 ), end of for loop. Then initialize another for loop to check the first character with value 1 from HashMap. if found then return the loop index else it will end the loop and return -1.

Java code

class Solution {
    public int firstUniqChar(String s) {
        char[] character = s.toCharArray();
        Map <Character, Integer> map= new HashMap<>();
        for(int i=0;i<character.length;i++){
            map.put(character[i],map.getOrDefault(character[i],0)+1);
        }
       for(int i=0;i<character.length;i++){
        if(map.get(character[i])==1){
            return i;
        }
       }
        return -1;
    }
}

Time & Space Complexity

Time Complexity: O(n)

Space Complexity: O(n)