Leetcode 387. How to Perform a Counting Using Array and Hash Table

Find the first non-repeating character's index in a string quickly using maps or arrays.

Problem statement

You have a string called s. Your objective is to locate the index of the first character in the string that does not repeat anywhere else in the string. If such a character doesn't exist, return -1.

Example 1

Input: s = "leetcode"
Output: 0

Example 2

Input: s = "loveleetcode"
Output: 2

Example 3

Input: s = "aabb"
Output: -1

Constraints

• 1 <= s.length <= 10^5.
• s consists of only lowercase English letters.

Solution 1: Using a map to store the appearances

Code

#include <iostream>
#include <unordered_map>
using namespace std;
int firstUniqChar(string s) 
{
    unordered_map<char, int> count;
    for (char& c : s) 
    {
        count[c]++;
    }
    for (int i = 0; i < s.length(); i++) 
    {
        if (count[s[i]] == 1) 
        {
            return i;
        }
    }
    return -1;
}
int main() 
{
    cout << firstUniqChar("leetcode") << endl;
    cout << firstUniqChar("loveleetcode") << endl;
    cout << firstUniqChar("aabb") << endl;
}

Output:
0
2
-1

Code explanation

1. The code initializes an unordered map count where characters from the string are keys, and their corresponding counts (how many times they appear in the string) are values.
2. The loop then iterates through the characters of the string s. For each character c encountered, it increments its count in the count map.
3. After counting all the characters in the string, it performs a second loop, this time using an index variable i that starts from 0 and goes up to the length of the string s.
4. In this loop, it checks whether the count of the character at the current index i is equal to 1. If it is, this means that the character is unique in the string, and the function returns i, which is the index of the first occurrence of that unique character.
5. If no unique character is found during the loop, the function returns -1 to indicate that there are no unique characters in the string.

Complexity

This solution has a time complexity of O(n), where n is the length of the string s, because it iterates through the string twice: once to count the characters and once to find the first unique character.

It also has a space complexity of O(k), where k is the number of distinct characters in the string, as it stores character counts in the count unordered map. As the problem considers only lowercase English letters, k = 26, you can give it O(1) complexity.

• Runtime: O(n), where n = s.length.
• Extra space: O(k), where k is the number of distinct characters in the string. If k=26, it is O(1).

Solution 2: Using an array to store the appearances

From the constraints "s consists of only lowercase English letters", you can use an array of 26 elements to store the counts.

Code

#include <iostream>
#include <vector>
using namespace std;
int firstUniqChar(string s) 
{
    // initializes an array of 26 elements, all set to zero
    std::array<int, 26> count{};
    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("leetcode") << endl;
    cout << firstUniqChar("loveleetcode") << endl;
    cout << firstUniqChar("aabb") << endl;
}

Output:
0
2
-1

Complexity

• Runtime: O(n), where n = s.length.
• Extra space: O(1) as the array's length is fixed 26.

Thanks for reading!

I hope you enjoyed this content. Don't keep it to yourself! Share it with your network and help each other improve your coding skills and advance your career!

Nhut Nguyen, the author of The Problem Solver's Guide To Coding.