O(n) solution ,java, using array as hashmap,so O(1) worst case to search in array


  • 0
    M
     public int lengthOfLongestSubstring(String s) {
            int a[][] = new int[256][2];
            int count=0;
            int maxCount = 0;
            int index =0;
            int prevIndex=0;
            while(index < s.length()){
                if(a[s.charAt(index)][0] == 0){
                    count++;
                    a[s.charAt(index)][0] = 1;
                    a[s.charAt(index)][1] = index;
                }else{
                    if(count>maxCount){
                        maxCount = count;
                    }
                    for (;prevIndex<=a[s.charAt(index)][1];prevIndex++){
                        count--;
                        a[s.charAt(prevIndex)][0] = 0;
                        a[s.charAt(prevIndex)][1] = 0;
                    }
                    count++;
                    a[s.charAt(index)][0] = 1;
                    a[s.charAt(index)][1] = index;
                }
                index++;
            }
            if(count>maxCount){
                maxCount = count;
            }
            
            return maxCount;
        }
    

    Here we use the property that ascii printable character range from 32 to 255, we store the index and status of whether the character already occurred or not in the string encountered so far, so we can tell that in O(1) , if we find that a character has already occurred, we can see what index we found it, and then from the index our string was selected till that, we re initialize our array till the previously found element and then continue.


Log in to reply
 

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