# First Unique Character in a String

Given a string `s` find the first non-repeating character in it and return its index . If it does not exist, return `-1`.

## Problem Statement

The problem is to find the index of the first non-repeating character in a given string `s`. If there is no such character, the function should return -1.

For example, if the input string is "leetcode", the first non-repeating character is 'l', and the function should return 0. If the input string is "loveleetcode", the first non-repeating character is 'v', and the function should return 2.

## Examples

Example 1:

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

Example 2:

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

Example 3:

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

## Clarifying Questions

1. Can you give me an example of input and expected output for this problem?

2. Are the characters in the string case-sensitive?

3. Can the string contain special characters or only alphabets?

4. Is there a constraint on the size of the input string?

5. Can I assume that the input string is non-empty?

## Solutions

Here are a few different approaches you could take to solve this problem:

1. Brute Force

2. Hash Map Approach

3. Two-Pass Hash Map Approach

4. Queue Approach

### Brute Force Approach:

One way to solve this problem is by iterating over the string and comparing each character with every other character in the string. This approach would have a time complexity of O(n^2), where n is the length of the input string.

#### Algorithm:

1. Iterate over each character in the string.
2. For each character, iterate over the entire string again to check if it's a non-repeating character.
3. If the character is non-repeating, return its index.
4. If there are no non-repeating characters, return -1.

Time and Space Complexity:

The Brute Force approach has a time complexity of O(n^2) since we are iterating over the string twice and checking each character against all the other characters. It has a space complexity of O(1) since we are not using any extra data structures.

### Hash Map Approach:

Another approach is to use a hash map to store the frequency of each character in the string. After building the hash map, we can then iterate over the string and check for the first character with a frequency of 1. This approach would have a time complexity of O(n), where n is the length of the input string.

#### Algorithm:

1. Create an empty hash map to store the frequency of each character.
2. Iterate over each character in the string and update its frequency in the hash map.
3. Iterate over the string again and check if the frequency of each character is 1.
4. If the frequency is 1, return the index of that character.
5. If there are no non-repeating characters, return -1.

Time and Space complexity:

The Hash Map approach has a time complexity of O(n) since we are iterating over the string only once and performing constant-time operations on the hash map. It has a space complexity of O(k) where k is the size of the character set, since we are using a hash map to store the frequency of each character.

### Queue Approach:

We can use a queue to store the characters and their frequency in the order they appear in the string. After building the queue, we can then iterate over the queue and check for the first character with a frequency of 1. This approach would have a time complexity of O(n), where n is the length of the input string.

#### Algorithm:

1. Create an empty queue to store the characters and their frequency in the order they appear in the string.
2. Iterate over each character in the string and update its frequency in the queue.
3. Iterate over the queue and check if the frequency of each character is 1.
4. If the frequency is 1, return the index of that character.
5. If there are no non-repeating characters, return -1.

Time and Space Complexity:

The Queue approach has a time complexity of O(n) since we are iterating over the string only twice (once to update the hash map and the queue, and once to dequeue the non-repeating characters) and performing constant-time operations on the hash map and the queue. It has a space complexity of O(k) where k is the size of the character set, since we are using a hash map to store the frequency of each character and a queue to store the indices of non-repeating characters.

Note that this approach uses a hash map to keep track of the frequency of each character and a queue to store the indices of non-repeating characters. We iterate over the string once to update the hash map and the queue. Then, we dequeue the indices from the queue and return the first one whose frequency is 1. This approach has a time complexity of O(n) since we are iterating over the string only twice. It is recommended for solving the problem for large strings when using a queue.

#### Algorithm:

1. Create a doubly linked list and initialize two pointers: head and tail.
2. Iterate over the input string character by character.
3. For each character:
1. Check if the character is already present in the linked list. If it is, remove the node from the list since it is no longer a non-repeating character.
2. If the character is not present in the list, create a new node for it and append it to the tail of the linked list.
4. After iterating over the entire string, the head of the linked list will point to the first non-repeating character in the string. If the head is NULL, then there are no non-repeating characters in the string.
5. Return the index of the first non-repeating character by iterating over the string again and comparing each character with the character at the head node of the linked list.

Note: In the C++ code, we use `unordered_map` instead of `Dictionary` and `queue` instead of `Queue`. We also use `length()` instead of `Length` to get the length of the string. The rest of the code follows the same logic and structure as the original code.

Time and Space Complexity:

The Linked List approach has a time complexity of O(n) since we are iterating over the string only once and performing constant-time operations on the hash map and the linked list. It has a space complexity of O(k) where k is the size of the character set, since we are using a hash map to store the frequency of each character and a linked list to store the indices of non-repeating characters.

In terms of time complexity, the Queue and Linked List approaches are the most efficient since they have a time complexity of O(n). However, the space complexity of both of these approaches is O(k), where k is the size of the character set. So if the character set is very large, then these approaches might not be the best choice in terms of space efficiency.

The Hash Map and Two-Pass Hash Map approaches have a space complexity of O(k), which is better than the Queue and Linked List approaches. They also have a time complexity of O(n), which is the same as the Queue and Linked List approaches. So, if space efficiency is a concern and the character set is not very large, then these approaches might be the best choice.

The Brute Force approach is the least efficient in terms of time complexity, with a time complexity of O(n^2), and does not use any extra space. However, it is only suitable for small inputs where the performance is not a major concern.

Overall, the Hash Map and Two-Pass Hash Map approaches are commonly used and provide a good balance between time and space efficiency, making them a popular choice for solving this problem.

Share: