最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：

s.length <= 40000
注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

滑动窗口解法

class Solution{
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<Character>();
        int max = 0;
        int count = 0;                                      //字串的字符数量
        int start = 0;                                      //字串开始时的位置
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!set.contains(c)) {
                set.add(c);
                count++;
            } else {
                max = Math.max(max, count);                 //每一次遇到重复元素，本次字符达到最大长度
                while (s.charAt(start) != c) {              //删掉集合中上一个与本次元素重复的元素之前的所有字符
                    set.remove(s.charAt(start));            //从集合删掉元素
                    start++;                                //起始位置后移一个
                    count--;                                //每删掉一个元素，减去一个计数
                }
                start++;                                    //从下一个字符开始
            }
        }
        max = Math.max(count, max);                         //判断最后一次的count和上一次的max哪个大
        return max;
    }
}

动态规划解法

状态转移如下:

1. 如果当前的字符串与先前的字符串重复了，那么找到当前字符串j的上一个位置i，当前最大的字符串的长度是j-i;

2. 如果当前的字符串与先前的字符串没有重复，那么最大字符串的长度是先前最大字符串长度+1

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1);          // 获取索引 i  
            dic.put(s.charAt(j), j);                            // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i;                // dp[j - 1] -> dp[j]    当获取的i的值为-1时(即不重复)，temp一定小于j-i,temp=temp+1,如果i的值不为-1，肯定有一个字符与j相同，这个字符在的位置应该在计算temp的开头或者往后的一个，这样的话temp的值应当大于等于j-i，去除重复元素之前的元素后的长度是j-i
            res = Math.max(res, tmp);                           // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

参考文献

jyd

作者：jyd
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信