# How to Perform a Counting Using Array and Hash Table

## [Problem statement](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)

[You have a strin](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)g [called `s`. Your ob](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)jective 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

```plaintext
Input: s = "leetcode"
Output: 0
```

### Example 2

```text
Input: s = "loveleetcode"
Output: 2
```

### Example 3

```text
Input: s = "aabb"
Output: -1
```

### Constraints

* `1 <`[`= s.length <= 10^5`.](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)
    
* [`s` consist](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)s of only [lowercase Englis](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)h letters.
    

## Solution 1: Using [a map to store th](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)e appearances

### Code

```cpp
#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;
}
```

```text
Output:
0
2
-1
```

### Code explanation

1. [The code initia](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)liz[es an unordered m](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)ap `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 iter[ates through the](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io) characters of the string `s`. For each character `c` encountered, it increments its count in the `count` map.
    
3. After counting all [the characters i](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)n 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 c[hecks whether the](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io) 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 chara[cter is found dur](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)ing the loop, the function returns -1 to indicate that there are no unique characters in the string.
    

### Complexity

This s[olution has a time complexity](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io) 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 spac[e complexity of `O`](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)`(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)`, whe[re `n = s.length`.](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)
    
* Extra space: `O(k)`, [where `k` is the n](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)umber of distinct characters in the string. If `k=26`, it is `O(1)`.
    

## Solution 2: Using [an array to store](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io) the appearances

From the constrain[ts "`s` consists of](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io) only lowercase English letters", you can use an array of 26 elements to store the counts.

### Code

```cpp
#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;
}
```

```plaintext
Output:
0
2
-1
```

### Complexity

* Runt[ime: `O(n)`, where `n = s.length`.](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)
    
* Extra space: `O(1)` [as the array's le](https://leetcode.com/problems/first-unique-character-in-a-string/?ref=leetsolve.ghost.io)ngth is fixed 26.
    

---

Thanks for reading! [**Get my book "10 Classic Coding Challenges"**](https://nhutnguyen.gumroad.com/l/10_classic) for FREE.