# First Unique Character in a String

Given a string find the index of the first unique character (non repeating).

For example,

For the string “see” the output is 0 since the letter s is not repeated in the string

For the string “bbaaddavt” the output is 7 because the letter v is not repeated and is present in index 7.

Assumption:

The given word contains only lower case English alphabets

Try out the solution here:

https://leetcode.com/problems/first-unique-character-in-a-string

Solution:

Convert the given string to a character array.

Then pass through each letter in the array twice.

During the first pass , create a frequency counter to store the number of times the character appears in the string.

You can use a map data structure or a primitive integer array (more efficient).

During the second pass check if the character frequency is one then return the index.

Here is the implementation using hash map:

```class Solution {
public int firstUniqChar(String s) {

Map<Character,Integer> m = new HashMap<>();

char[] arr = s.toCharArray();

for(char c:arr){

m.put(c,m.getOrDefault(c,0)+1);

}

for(int i=0;i<arr.length;i++){

if(m.get(arr[i]) == 1) return i;
}

return -1;
}
}
```

Here is the implementation using an integer array:

```class Solution {
public int firstUniqChar(String s) {

int[] freq = new int;

char[] arr = s.toCharArray();

for(char c:arr){

freq[c - 'a']++;

}

for(int i=0;i<arr.length;i++){

if(freq[arr[i] -'a'] == 1) return i;
}

return -1;
}
}
```

Time complexity:

In both the cases we make two passes along the array.

So time complexity is O(n)

Space complexity:

In both the cases we use an extra data structure to store the frequency of English letters . As per assumption we have only lower case English letters to deal with . The total storage capacity is 26 and is a constant.

So space complexity is O(1)

That’s it!

Posted

in

by

Tags: