True O(1) space and O(n) solution


  • 0
    J

    The idea is to use a int array as hashtable where storing indices having been traversed.
    Need to check whether charToIndex[c] < left because charToIndex[c] maybe the "out-of-date".

    public int lengthOfLongestSubstring(String s) {
            int[] charToIndex = new int[256];
            Arrays.fill(charToIndex, -1);
            int len = 0;
            int left = 0;
            for (int right = 0; right < s.length(); right++) {
                char c = s.charAt(right);
                if (charToIndex[c] == -1 || charToIndex[c] < left) {
                    charToIndex[c] = right;
                    if (right - left + 1 > len) len = right - left + 1;
                } else {
                    left = charToIndex[c] + 1;
                    charToIndex[c] = right;
                }
            }
            return len;
        }
    

Log in to reply
 

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