Easy to understand One Pass solution O(n + 26) in Java


  • 0
    S

    In the two pass solution, we have to scan through the string twice, which is O(2*n). If the unique character appears at the end of the string, this two pass solution will not be very good.

    We are able to just scan the string by once by recording both the counts of each character and the first index the char occurs in the string in O(n). Then, we scan the aggregated result in O(26). The total complex is O(26) + O(n).

    When the string is very long, this method can save half time.

    public class Solution {
        // //two passes
        // public int firstUniqChar(String s) {
        //     int[] counts = new int[26];
            
        //     for (int i = 0; i < s.length(); i++) {
        //         counts[s.charAt(i) - 'a']++;
        //     }
            
        //     for (int i = 0; i < s.length(); i++) {
        //         if (counts[s.charAt(i) - 'a'] == 1) return i;
        //     }
            
        //     return -1;
            
        // }
        
        //one pass solution of the string,
        public int firstUniqChar(String s) {
            //each row records the number of occurence of this char and the first index it appears
            //countIndex[i][0]: number of times this char occurs
            //countIndex[i][1]: the index where the first ime the char occurs
            int[][] countsIndexes = new int[26][2];
            
            
            //scan through the string O(n)
            for (int i = 0; i < s.length(); i++) {
                int index = s.charAt(i) - 'a';
                int[] countIndex = countsIndexes[index];
                //if the char has not occured yet
                if (countIndex[0] == 0) {
                    countsIndexes[index][0] = 1;
                    countsIndexes[index][1] = i;
                }
                else {
                    //if this char occurs multiple times, set the index to -1
                    countIndex[1] = -1;
                }
            }
            
            int minIndex = s.length();
            //Scan through the countsIndex, O(26)
            for (int[] countIndex : countsIndexes) {
                if (countIndex[0] != 0 && countIndex[1] >= 0) minIndex = Math.min(minIndex, countIndex[1]);
            }
            
            return minIndex == s.length() ? -1 : minIndex;
            
        }
    }
    

Log in to reply
 

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