Java O(n) solution, using two pointers and map


  • 0
    M

    Idea: map contains the last position in s for each character. Use two pointers to record the left and right side of the substring. The maximum of the length of substrings is the result.
    Time Complexity: O(n)

        public int lengthOfLongestSubstring(String s) {
            //check s null or empty
            if(s==null || s.length()==0) return 0;
            //assume s only contains ascii 
            int[] map = new int[256];
            Arrays.fill(map, -1);
            int maxLen = 0;
            for(int l=0, r=0; r<s.length(); r++){
                char ch = s.charAt(r);
                if(map[ch] >= 0) { //contains repeating character
                    l = Math.max(l, map[ch]+1); //l will only increase, in case repeating character appears before l
                } 
                map[ch] = r;
                maxLen = Math.max(maxLen, r-l+1);
            }
            return maxLen;
        }
    

Log in to reply
 

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