Solution For First Unique Character In A String

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.

Approach:

We can solve this problem by using a hashmap to keep track of the count of each character in the string. Then, we can iterate over the string again and return the index of the first character whose count is one.

Algorithm:

1. Initialize a hashmap to keep track of the count of characters in the string.
2. Iterate over the string s and increment the count for each character in the hashmap.
3. Iterate over the string again and return the index of the first character whose count is one.
4. If no such character is found, return -1.

Code:

Python:

“`
class Solution:
def firstUniqChar(self, s: str) -> int:
# Step 1: Initialize a hashmap to keep track of the count of characters in the string.
char_count = {}

    # Step 2: Iterate over the string s and increment the count for each character in the hashmap.
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1

    # Step 3: Iterate over the string again and return the index of the first character whose count is one.
    for i, char in enumerate(s):
        if char_count[char] == 1:
            return i

    # Step 4: If no such character is found, return -1.
    return -1

“`

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string s. We iterate over the string twice, once to build the hashmap and once to find the first non-repeating character. The time complexity of building the hashmap is O(n) and finding the first non-repeating character is also O(n).
• Space Complexity: O(n), where n is the length of the string s. We are using a hashmap to store the count of characters in the string, which can have a maximum of n distinct characters. Therefore, the space complexity is O(n).

Step by Step Implementation For First Unique Character In A String

class Solution {
  public int firstUniqChar(String s) {
        HashMap count = new HashMap();
        int n = s.length();
        // build hash map : character and how often it appears
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        
        // find the index
        for (int i = 0; i < n; i++) {
            if (count.get(s.charAt(i)) == 1) 
                return i;
        }
        return -1;
    }
}

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # Edge case where string is empty
        if not s:
            return -1
        
        # Hashmap to keep track of counts of each character
        counts = {}
        
        # Iterate through string, adding each character to hashmap
        for char in s:
            counts[char] = counts.get(char, 0) + 1
        
        # Iterate through string again
        for i, char in enumerate(s):
            # If character only appears once, return index
            if counts[char] == 1:
                return i
        
        # If no unique characters found, return -1
        return -1

var firstUniqChar = function(s) {
    
    // create a hashmap to store the count of each character
    let hashmap = {};
    
    // fill the hashmap with the count of each character
    for(let i = 0; i < s.length; i++) {
        if(hashmap[s[i]]) {
            hashmap[s[i]]++;
        } else {
            hashmap[s[i]] = 1;
        }
    }
    
    // loop through the string and return the first character with a count of 1
    for(let i = 0; i < s.length; i++) {
        if(hashmap[s[i]] === 1) {
            return i;
        }
    }
    
    // if no unique characters are found, return -1
    return -1;
};

class Solution {
public:
    int firstUniqChar(string s) {
        // Initialize a map to keep track of the number of times
        // each character appears in the string
        unordered_map charCount;
        
        // Iterate through the string, incrementing the count
        // for each character
        for (char c : s) {
            charCount[c]++;
        }
        
        // Iterate through the string again, this time returning
        // the index of the first unique character
        for (int i = 0; i < s.length(); i++) {
            if (charCount[s[i]] == 1) {
                return i;
            }
        }
        
        // If no unique character is found, return -1
        return -1;
    }
};

public class Solution {
    public int FirstUniqChar(string s) {
        //Create a dictionary to store each character and its frequency
        Dictionary dict = new Dictionary();
        
        //Loop through the string and store each character in the dictionary
        for(int i = 0; i < s.Length; i++){
            if(dict.ContainsKey(s[i])){
                dict[s[i]]++;
            }
            else{
                dict[s[i]] = 1;
            }
        }
        
        //Loop through the string again and return the index of the first character with a frequency of 1
        for(int i = 0; i < s.Length; i++){
            if(dict[s[i]] == 1){
                return i;
            }
        }
        return -1;
    }
}