Share my short and fast Java code with brief explanation


  • 0
    M
    /*
        imagine a dynamic-sized sliding window, in which each character is unique.
        expand the window using its right pointer, shrink it using its left pointer.
    */
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int max = 0, left = 0, right = 0;
            boolean[] inSubstring = new boolean[256];
            while (true) {
                if (right < s.length() && !inSubstring[(int)s.charAt(right)]) {  // expand the window towards right
                    inSubstring[(int)s.charAt(right++)] = true;
                }
                else {
                    max = Math.max(max, right - left);
                    if (right == s.length()) { break; }  // now s[right] is in the substring
                    for (; s.charAt(left) != s.charAt(right); ++left) {  // char s[right] is in s[left...right)
                        inSubstring[(int)s.charAt(left)] = false;
                    }
                    inSubstring[(int)s.charAt(left++)] = false;
                }
            }
            return max;
        }
    }

Log in to reply
 

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