leetcode-3 无重复字符的最长子串_leetcode 3 无重复字符的最长子串 动态规划解法

leetcode-3 无重复字符的最长子串

题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

• 示例：

示例 1:
​
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
​
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
​
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
​
输入: s = ""
输出: 0

解题思路

解法一：

暴力求解，就是把给定字符串的所有子字符串都依次计算其最长无重复的最长子串，就是相当于把每种情况都算一下。

1. 因为要列举出所有子字符串的情况，所以用俩层for循环去确定子字符串的开头和结尾位置，然后把开头和结尾的下标交给substring方法生成子字符串

2. 接下来就需要考虑怎么去判断截取的子字符串里面是否有重复的元素，这里我用的是长度比较法，利用了set集合的不可重复性的特点把set集合的元素个数和截取的子字符串长度进行比较，如果set集合元素的个数小于原本字符串的长度，就证明有重复的元素被筛选下去了，就证明他不满足最长无重复的特点，否则就是长度相等，证明没有重复的元素，就可以把当前字符串的长度。与之前记录的长度进行比较，谁更长就要谁。

3. 大体功能已经具备，进行一点小小的优化。俩层for循环确定位置，第一层确定的是开头截取的位置，第二行是截取的末尾的位置，但是如果说在截取的子字符串里面发现了重复的元素呢，以这个为开头位置的子字符串就都不用进行比较了，因为无论怎么往后取，都一定包含重复元素，所以就可以提前结束里层循环。

• 实现代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        Set<Character> set = new HashSet<>();
        for(int i = 0;i < s.length();i++){
            for(int j = i + 1;j <= s.length();j++){
                String sonString = s.substring(i,j);
                char[] chars = sonString.toCharArray();
                for(char c : chars){
                    set.add(c);
                }
                if(set.size() == sonString.length()){
                    maxLength = Math.max(maxLength,sonString.length());
                }else{
                    set.clear();
                    break;
                }
            }
        }  
        return maxLength;  
    }
}

解法二

这个解法是百度的，效率要比上面高的多。我理解了好久，理解的地方就直接在代码里面写出来了。

• 代码

/**
第八行的代码我理解了好一会,我刚开始认为写下面那句就可以，但是运行了一下。走了一下错误的例子才发现问题。例：abba abb的时候都没有问题，唯一考虑一下的就是这个left的作用，其实起的就是一个标记的作用当出现重复字符的时候标记下一位，方便去跟之前的串比较谁更长，这用下面那句就可以实现了。
*/
/**
但是当最后一个a进去就不一样了，因为如果你直接去计算left的话，之前的标记点left会被覆盖掉，那样就会导致中间的重复字符串bb被跳过去了。直接将将标记落在了第一个b上面，这显然是不行的，因此需要将新计算的left与新计算得到的left进行一个比较，谁大取谁
*/
class Solution {
    public int lengthOfLongestSubstring(String s) {  
​
        HashMap<Character,Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        for(int i = 0;i < s.length();i++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
                //left = map.get(s.charAt(i)) + 1;
            }
            map.put(s.charAt(i),i);
            max = max > i - left + 1 ? max : i - left + 1;
        }
        return max;
        
    }
}