My JAVA accepted code O(n)


  • 0
    V
    public class Solution {
        boolean[] letter;
        int maxlen = 1;
    
        public int lengthOfLongestSubstring(String s) {
            if (s.length() == 0) return 0;
            if (s.length() == 1) return 1;
    
            letter = new boolean[128]; // for ASCII encoding string, default values are all false
    
            int i = 0;
            letter[s.charAt(0)] = true;
            
            int j = 1;
            while(j < s.length()){
                if (letter[s.charAt(j)]){ // repeated character
                    while(i < j){
                        if (s.charAt(i) == s.charAt(j)){ // update i
                            i++;
                            break;
                        }else{
                            letter[s.charAt(i)] = false;
                            i++;
                        }
                    }
                }else{ // if no repeat, the length is suceessfully advance one step
                    letter[s.charAt(j)] = true;
                    update(j-i+1);
                }
                j++;
            }
            return maxlen;
        }
    
        private void update(int len){
            if (len > maxlen) maxlen = len;
        }
    }
    

    Instead of using HashMap to check unique characters, I use ASCII boolean array to store the substring letter existence. Step by step moving pointer j. If pointer j encounters a repeated letter, pointer i is moving until the repeated letter is cross over or i reach out j (in the same position).


Log in to reply
 

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