Longest Substring Without Repeating Characters(Medium)没有重复字符的最长子串

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.

Leetcode Source

解题思路：

1. 当碰到一个重复字符时（假设它的索引是j），就是说当前的子串（j-i）是潜在的最大子串。同时也说明重复字符已经在j之前出现，它的位置i<=k<j。
2. 同时额说明从k开始或从k之前字符位置开始的子串将小于j-i，因而求下一个子串可用从k+1开始。

Java代码：

int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int i = 0, j = 0;
    int maxLen = 0;
    boolean[] exist = new boolean[256];
    while (j < n) {
        if (exist[s.charAt(j)]) {
            maxLen = Math.max(maxLen, j-i);
            while (exist[s.charAt(i)] != exist[s.charAt(j)] ) {
                exist[s.charAt(i)] = false;
                i++;
            }
            i++;
            j++;
        } else {
            exist[s.charAt(j)] = true;
            j++;
        }
    }

    maxLen = Math.max(maxLen, n - i);
    return maxLen;
}