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:
- Initialize a hashmap to keep track of the count of characters in the string.
- Iterate over the string s and increment the count for each character in the hashmap.
- Iterate over the string again and return the index of the first character whose count is one.
- 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) { HashMapcount = 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_mapcharCount; // 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 Dictionarydict = 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; } }