#### Approach #1 using Two-pass hash table

**Intuition**

Check all the characters in the string one by one and insert in HashMap with character as the key and index as the value. If a key repeats, set its value to -1.

**Algorithm**

Suppose we have a function intUniqChar(String S) . It returns the first unique character index.

- Convert the string to char array and add all the characters to LinkedHashMap (to maintain the order).key is the character and value is the index.

If a key already exists set its value to -1. - Add all the values to a LinkedList to maintain the order.
- Find the first element from the list whose value is not equal to -1.
- That value will be the index of first unique character in the string

**Java**

```
import java.util.Optional;
class Solution {
public int firstUniqChar(String s) {
if (s.isEmpty())
return -1;
char[] charArray = s.toCharArray();
Map<Character, Integer> map = new LinkedHashMap<>();
// Adding the characters to a LinkedHashMap
for (int i = 0; i < charArray.length; i++)
{
if(!map.containsKey(charArray[i]))
{
map.put(charArray[i],i);
}
else
{
map.put(charArray[i],-1);
}
}
List<Integer> values = new LinkedList<>();
// Adding all the values in map to a LinkedList.
values.addAll(map.values());
// filtering the -1 indices and returning the first index.
Optional<Integer> output = values.stream()
.filter(x -> !x.equals(-1)).findFirst();
if(output.isPresent())
return output.get();
else return -1;
}
}
```

**Complexity Analysis**

- Time complexity : O(n)

To verify if characters have duplicates, we need to read each character exactly once and it will lead to linear complexity which is O(n)

- Space complexity : O(2m) (m <= lengthOfString)

Since we insert all the unique characters only once in the HashMap which is m and also add all the values to LinkedList which is again m.

So the space complexity is O(2m).