3. Longest Substring Without Repeating Characters

[LLancelot]

题目: 无重复字符的最长子串

Given a string, find the length of the longest substring without repeating characters.
Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

双指针思路

• 双指针方法，left = 0， right = 0，max = 0，定义一个长度为128的 boolean[] used 数组，来表示字符串中哪些字符（ASCII 为 0~127）被使用过。
• 用 s.charAt(right) 表示当前字符，right 从头遍历到尾。
• 若当前字符不在 used 中，则将该字符在 used 中标记为 true，并且 right ++
• 若当前字符在 used 中 （已经在前面出现过），
  首先，将max值更新， max = Math.max(max, right - left) 然后，我们需要处理 left，并且要一直移动 left 直到 left 对应的字符与当前字符重复为止，比如 “abcdbe”，因为“abcd” 中每个字符均在扫描时使用了一次，所以这个阶段都是 right 指针在移动，left 指针依旧处于 0 的位置，接着 right 来到字符 ‘b’ ，发现 b 已被使用，我们需要做的是让 left 来到第一个 'b' 的位置，即让 left = 1。此时，left 和 right 都已经指向了相同的字符‘b’，下一步我们的目的是要把 left 和 right 同时右移一位，以保证 [left, right) 区间不再有重复现象。
• 循环 right 一直向后，直到结束循环，最终再更新一次 max 的值。

Code

// Two Pointer
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0)    return 0;
        int n = s.length();
        int left = 0, right = 0;
        int max = 0;
        boolean[] used = new boolean[128];
        
        while (right < n) {
            if (used[s.charAt(right)] == false) {
                used[s.charAt(right)] = true;
                right++;
            }
            else {
                max = Math.max(max, right-left);
                while (left < right && s.charAt(left)!= s.charAt(right)) {
                    used[s.charAt(left)] = false;
                    left++;
                }
                // find same char
                left++;
                right++;
            }
        }
        // lastly, update max
        max = Math.max(max, right - left);
        return max;
    }
}