Java two pointers (slow and fast) solution (18 ms)


  • 11

    The idea is to use a slow pointer to point to the current unique character and a fast pointer to scan the string. The fast pointer not only just add the count of the character. Meanwhile, when fast pointer finds the identical character of the character at the current slow pointer, we move the slow pointer to the next unique character or not visited character. (20 ms)

    public class Solution {
        public int firstUniqChar(String s) {
            if (s==null || s.length()==0) return -1;
            int len = s.length();
            if (len==1) return 0;
            char[] cc = s.toCharArray();
            int slow =0, fast=1;
            int[] count = new int[256];
            count[cc[slow]]++;
            while (fast < len) {
                count[cc[fast]]++;
                // if slow pointer is not a unique character anymore, move to the next unique one
                while (slow < len && count[cc[slow]] > 1) slow++;  
                if (slow >= len) return -1; // no unique character exist
                if (count[cc[slow]]==0) { // not yet visited by the fast pointer
                    count[cc[slow]]++; 
                    fast=slow; // reset the fast pointer
                }
                fast++;
            }
            return slow;
        }
    }
    

  • 0

    Improved version, which checks early termination when all characters from 'a'~'z' appear more than twice. (18 ms)

    public class Solution {
        public int firstUniqChar(String s) {
            if (s==null || s.length()==0) return -1;
            int len = s.length();
            char[] cc = s.toCharArray();
            int slow =0, fast=1;
            int[] count = new int[256];
            int total = 0;
            count[cc[slow]]++;
            while (fast < len) {
                count[cc[fast]]++;
                if (cc[fast] == cc[slow]) { 
                    total++;
                    if (total==26) return -1;
                    while (slow < len && count[cc[slow]] > 1) slow++;
                    if (slow >= len) return -1;
                }
                if (count[cc[slow]]==0) count[cc[slow]]++;
                if (slow > fast) fast=slow;
                fast++;
            }
            return slow;
        }
    }
    

  • 9

    One pass solution, 18 ms.
    Instead of storing the count, the array stores the first appearance index (1-based).
    The index set to -1 if a letter appears more than once. 0 means a letter does not exist.

    public class Solution {
        public int firstUniqChar(String s) {
            if (s==null || s.length()==0) return -1;
            int len = s.length();
            int[] idx = new int[26];
            int total = 0;
            int i = 1;
            for (char c: s.toCharArray()) {
                int off = c-'a';
                if ( idx[off] == 0) {
                    idx[off] = i;
                } else if ( idx[off] > 0 ) {
                    idx[off] = -1;
                    if (++total == 26) return -1;
                } 
                i++;
            }
            int ret = len+1;
            for (int res : idx ) {
                if ( res > 0 ) ret=Math.min(ret, res);
            }
            return ret == len+1? -1 : ret-1;
        }
    }
    

  • 0
    Z

    Is the time complexity O(n^2) ?


  • 0

    @zfrancica No, it is O(2*n).


  • 0
    Q

    Do not use 'new int[26]' in real world. Instead use something like hash table.


  • 2

    @qzhang72 I think the idea is to be as efficient as possible and if the known bounds are lowercase letters than the most efficient will be 26 sized int array. If you need to cover all possible characters the most efficient will be 256 sized int array. A real HashTable object will surely be fast but not as optimal as a simple array, it never will.


  • -1
    Z

    How about this?

    public class Solution {
        public int firstUniqChar(String s) {
            if (s.isEmpty()) return -1;
            int[] tracking = new int[26];
            int currInd = 0, ansInd = 0, n = s.length();
            while(currInd < n) {
                char c = s.charAt(currInd);
                if (++tracking[c - 'a'] > 1) {
                    while(c == s.charAt(ansInd) || tracking[s.charAt(ansInd) - 'a'] > 1) {
                        if(++ansInd >= n) return -1;
                    }
                }
                currInd++;
            }
            return ansInd;
        }
    }
    

  • 1
    L

    @yubad2000
    Inspired by your solution. Thanks for sharing it. However, the second if condition in the while loop is not necessary.

    
        public int firstUniqChar(String s) {
            if(s==null || s.length()==0) return -1;
            int len = s.length();
            int slow = 0,fast = -1;
            int[] count = new int[256];
            char[] c = s.toCharArray();
            while(++fast < len){
                count[c[fast]] ++;
                while(slow<len && count[c[slow]]>1) slow++;
                if(slow ==len) return -1;
            }
            return slow;
        }
    
    

    This still works with same time complexity.


Log in to reply
 

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