3. Longest Substring Without Repeating Characters

题目

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.

题目大意

在一个字符串重寻找没有重复字母的最长子串。

解题思路

这一题和第 438 题，第 3 题，第 76 题，第 567 题类似，用的思想都是”滑动窗口”。

滑动窗口的右边界不断的右移，只要没有重复的字符，就持续向右扩大窗口边界。一旦出现了重复字符，就需要缩小左边界，直到重复的字符移出了左边界，然后继续移动滑动窗口的右边界。以此类推，每次移动需要计算当前长度，并判断是否需要更新最大长度，最终最大的值就是题目中的所求。

代码解析

简单解法

class Solution {

    public int lengthOfLongestSubstring(String s) {
        String str = "";
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            String c = Character.toString(s.charAt(i));
            if (str.contains(c)) {
                int index = str.indexOf(c);
                str = str.substring(index + 1);
                str += c;
            } else {
                str += c;
            }
            if (str.length() > max) {
                max = str.length();
            }
        }
        return max;
    }
}

优化解法

class Solution {

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap();
        int max = 0;
        //left 滑动窗口左边界， right 正在滑动的索引（右边界）
        for (int left = 0, right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                // map.get(c)+1 可能比 i 还小，通过 max 函数来锁住左边界
                //在"tmmzuxt"这个字符串中, 遍历到“tmm”时 左边界更新为“tm”后面“m”的位置
                //遍历到”tmmzuxt“时，map.get(c)会取到第一个t的位置，但是他已经不在left里面
                //因此这时窗口应该为“mzuxt”，左边界还是“m”的位置
                left = Math.max(left, map.get(c) + 1);
            }
            //会更新重复值的索引位置，下次遇到重复值时，左窗口将移动
            //遍历到”tmmzuxt“后下一个如果还是t那么窗口将从“tm|mzuxt|t”滑动到“tmmzuxt|t|”的位置
            map.put(c, right);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}