Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.


two pointer构建sliding window 初始化为 [0, 0]. Increasing right side from 0  to length - 1. 如果新加的char已存在于现窗口中，则update longest length，同时adjust left side。
improvement: 用int[26]数组储存char出现的位置, update left side 为table里面当前duplicate char的位置+1。

Code:

public class Solution {

    public int lengthOfLongestSubstring(String s) {

        // Start typing your Java solution below

        // DO NOT write main() function

        int i = 0, j, longestLength = 0;

        int[] flag = new int[26];

        

        for(j = 0; j < s.length(); j++){

            int index = s.charAt(j) - 'a';

            // duplicate char

            if(flag[index] != 0){

                longestLength = Math.max(j-i, longestLength);

                // adjust left side of window

                while(i < flag[index]){

                    flag[s.charAt(i) - 'a'] = 0;

                    i++;

                }

            }

            flag[index] = j + 1;

        }

        longestLength = Math.max(j-i, longestLength);

        return longestLength;

    }

}