Java Straightforward O(n) runtime O(1) space solution


  • 2
    N

    Use two arrays to keep track of the frequency and location of each char in s. In the second loop, get the min location of frequency 1.

    public int firstUniqChar(String s) {
        int n = s.length();
        int[] alp = new int[26];
        int[] loc = new int[26];
        
        for (int i = 0; i < n; ++i) {
            alp[s.charAt(i) - 'a']++;
            loc[s.charAt(i) - 'a'] = i;
        }
        
        int ret = -1;
        for (int i = 0; i < 26; ++i) {
            if (alp[i] == 1) {
                ret = ret == -1 ? loc[i] : Math.min(ret, loc[i]);
            }
        }
        
        return ret;
    }

  • 0
    B

    Doesn't the extra array used to keep track of frequency invalidate the O(1) space claim?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.