Sponsored
Sponsored
This approach employs a hash map to store the frequency of each character in the string. Then, by iterating through the string again, we can find the first character with a frequency of 1 and return its index. If no such character is found, we return -1.
Time Complexity: O(n), where n is the length of the string, as we traverse through the string twice.
Space Complexity: O(1), because the array size is constant (26 letters of the English alphabet).
1using System;
2using System.Collections.Generic;
3
4public class FirstUniqueCharacter {
5 public static int FirstUniqChar(string s) {
6 Dictionary<char, int> freq = new Dictionary<char, int>();
7 foreach (char c in s) {
8 if (freq.ContainsKey(c)) {
9 freq[c]++;
10 } else {
11 freq[c] = 1;
12 }
13 }
14 for (int i = 0; i < s.Length; i++) {
15 if (freq[s[i]] == 1) {
16 return i;
17 }
18 }
19 return -1;
20 }
21
22 public static void Main(string[] args) {
23 string s = "leetcode";
24 Console.WriteLine(FirstUniqChar(s));
25 }
26}This solution in C# employs a Dictionary to track the frequencies of characters. We then check for the first character with a frequency of 1 and return its index.
This approach involves iterating through the input string two times without using any auxiliary space like a hash map or dictionary. In the first iteration, we use an array to count the occurrences of each character. In the second iteration, we check for the first character that appears only once by referring to the count array. We conclude by returning its index or -1 if no such character is found.
Time Complexity: O(n)
Space Complexity: O(1)
#include <vector>
#include <string>
using namespace std;
int firstUniqChar(string s) {
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
for (int i = 0; i < s.length(); ++i) {
if (count[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
int main() {
cout << firstUniqChar("loveleetcode") << endl;
return 0;
}For this C++ solution, a vector is used to tally character frequencies for each letter based on their indices. A second loop reveals the index where the first unique character occurs.