387.md

387. First Unique Character in a String

Description

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Thinking Process

1. Scan through the string once, update the frequency of each character
2. Scan through the string another time, return the index if the character has a frequence of 1

Code

public class Solution {
    public int firstUniqChar(String s) {
        int[] freq = new int[26];
        for(int i = 0; i < s.length(); i++){
            freq[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s.length(); i++){
            if(freq[s.charAt(i) - 'a'] == 1)
                return i;
        }
        return -1;
    }
}

Complexity

1. Space complexity is O(1) since we only use constant extra space
2. Time complexity is O(n) as the string is scanned twice