子串问题题解汇总 ---通俗易懂版

找到字符串的最长无重复字符子串

https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=190&&tqId=35220&rp=1&ru=/ta/job-code-high-rd&qru=/ta/job-code-high-rd/question-ranking

本文参考了几篇题解区大佬的文章，对以下做过的子串问题进行解析和总结。

图片说明

找到字符串的最长无重复字符子串

图片说明

方法一 滑动窗口法：

我们可以使用双指针模拟一个滑动窗口。
初始化窗口为 (left, right]。所以left从-1开始。
窗口不断往右扩大。
根据题目的要求，即遇到有重复数字的，在窗口左侧缩小。
在每次滑动时，对窗口的大小进行比较，保留最大的长度。

代码实现：

   public int maxLength (int[] arr) {
        int res = 0, left = -1;
        //用来存放窗口存放过的数字
        HashMap<Integer, Integer> windows = new HashMap<>();
        //窗口不断往右移
        for(int right = 0; right < arr.length; right++){
            //根据题目，当遇到重复的数字时，缩小左侧窗口
            if( windows.containsKey(arr[right])){
                //因为我们有可能遇到索引比left原来还小的相同数字
                //所以这里要进行比较，目的还是为了缩小左侧窗口，确保窗口内全是不重复的数字
                left = Math.max(left, windows.get(arr[right]));
            }
            //更新窗口内数字的索引
            windows.put(arr[right], right);
            //right-left是窗口大小
            //因为要找最长，所以要进行比较
            res = Math.max(res, right-left);

        }
        return res;
    }

方法二 **双指针+回头遍历**：

过程可以看注释

    public int maxLength (int[] arr) {
         int res = 0, tmp = 0;
        //right指针往右移动
        for(int right = 0; right < arr.length; right++){
            int left = right - 1;
            //回头扫描，要是没有找到相同的，左指针一直倒退
            while(left >= 0 && arr[right] != arr[left])
                left--;
            //暂时保存子串长度 
            //若指针距离比上一个字符时拥有的子串长度大，就tmp + 1，否则就设置为指针距离，方便下一步res进行比较
            tmp = tmp < right - left ? tmp + 1 : right - left;
            res = Math.max(res,tmp);
        }
        return res;

最长公共子串

图片说明

这道题有点类似 最长公共子序列。

公共子串和公共子序列的区别

公共子串：必须是连续的。
公共子序列：不必是连续的，但是相对位置必须不能改变。

好，接下来，我们上动态规划解法：

其实解法跟最长公共子序列的是差不多的。

先确定状态和选择
- 状态有两个，分别是str1 和 str2 的索引 i,j 变化
- 选择有两个，当str1[i-1] 和 str2[j-1]相等时，dp[i][j] + 1；当不相等时，dp[i][j]置为0。
确定状态转移方程和 base case
- 这里画个图就清晰多了
  
  当字符相等时，dp[i][j] = dp[i-1][j-1] + 1；
  不相等时，dp[i][j] = 0
- base case：dp[0][j] 和 dp[i][0] 全部置为0。

代码实现：

public String LCS(String str1, String str2){
    if(str1.length() == 0 || str2.length() == 0){
        return "-1";
    }
    //起始位置
    int start1 = 0;
    //偏移量
    int max = 0;
    int len1 = str1.length();
    int len2 = str2.length();

    int[][] dp = new int[len1+1][len2+1];

    for(int i = 1; i <= len1; i++){
        for(int j = 1; j <= len2; j++){
            if(str1.charAt(i-1) == str2.charAt(j-1)){
                  //将当前相等的字符计入 + 1
                  dp[i][j] = dp[i-1][j-1] + 1;
            }else {
                dp[i][j] = 0;
            }

            if(max < dp[i][j]){
                //max记录已经拥有的子串长度 
                max = dp[i][j];
                //因为字符串索引是从0开始的，所以 i - max 刚好是起始位置
                start1 = i - max;

            }
        }
    }
    if(max == 0) return "-1";
    return str1.substring(start1, max+start1);
}

最长回文子串

图片说明

代码实现：

public class Palindrome {
    public int getLongestPalindrome(String A, int n) {
        int res = 0;
        //暴力解法
        for(int i = 0; i < n; i++){
            for(int j = i+1; j <= n; j++){
                String tmp = A.substring(i,j);
                //调用判断是否为回文子串的方法
                if(isPalindrome(tmp)){
                    res = Math.max(res, tmp.length());
                }
            }
        }
        return res;
    }

    public boolean isPalindrome(String s) {
        int len = s.length();
        for(int i=0; i< len/2; i++){
            if(s.charAt(i) != s.charAt(len-1-i))
                return false;
        }
        return true;
    }
}

回文问题
寻找最长回文子串，不是求长度

其实大同小异，也是同样使用双指针法

public class Palindrome{
    String res;
    public String longest(String s){
        res = new String();
        for(int i = 0; i < s.length(); i++){
            //寻找长度为基数的回文子串
            String s1 = String palindrome(s, i, i);
            //寻找长度为偶数的回文子串
            String s2 = String palindrome(s, i, i+1);
            res = res.length() > res : s1;
            res = res.length() > res : s2;
        }
        return res;
    }

    public String palindrome(String s, int l, int r){
        while( l >= 0 && r < s.length(); && s.charAt(l) == s.charAt(r)){
            l--; r++;
        }
        return s.subString(l, r+1);
    }

}

最长回文串不是子串

图片说明

class Solution {
    public int longestPalindrome(String s) {
        //因为在ASCII码中，A到z是65到122 总共58个
        int[] cnt = new int[58];

        for(char c : s.toCharArray()){
            cnt[c - 'A'] += 1;
        }
        int ans = 0;
        for(int x : cnt){
            //如果是偶数 就ans+x; 如果是奇数 就减掉一个再ans+x
            ans += x - (x & 1);
        }
        //回文串要么全是偶数个数 要么除了偶数个数外，只有一个奇数
        return ans < s.length() ? ans + 1 : ans;
    }
}

最长的括号子串

图片说明

绝了这道题，一开始写了个使用栈的解法，测试一直过不了。后来看了题解，才发现自己理解错题目了呜呜呜。上正确解法：

方法一 使用栈 ：
这个应该是很容易想到的解法

栈存放的是括号的索引。
当遇到 '('时，入栈，当遇到 ')'时，如果栈为空，将它放进去；否则弹出栈顶，再将当前索引减去栈顶的索引，再跟原来的res进行比较，更新res值，保证取到最大的数字。

代码实现：

    public int longestValidParentheses (String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i=0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            } else {
                stack.pop();
                if(stack.empty()) {
                    stack.push(i);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }           
        }
        return res;
    }

方法二 动态规划：

dp数组存放的是当前所拥有的括号子串长度。
在动态规划框架上，处理了三种情况：

当前字符为 '('，跳过，默认初始化为0;
当前字符为 ')'，又分为两种情况：
- 当前面只有单个'()'出现或者判断字符正处于嵌套括号的最里层时，dp[i] = dp[i-2] + 2；
- 当处于嵌套括号的外层时， dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2；

代码实现：

    public int longestValidParentheses (String s) {
        int res = 0;
        int[] dp = new int[s.length()];
        for(int i = 1; i < s.length(); i++){
            //只对当前字符是')'进行处理
            if(s.charAt(i) == ')'){
                //当()时
                 if(s.charAt(i-1) == '('){
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                 } else if(i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '('){ //当 (())时
                    dp[i] = dp[i-1] + ((i-dp[i-1]) >= 2 ? dp[i - dp[i-1] - 2] : 0) + 2;
                 }
                 res = Math.max(res, dp[i]);
            }
        }
        return res;
    }

最长的覆盖子串

这道题也可以用滑动窗口方法：
与第一题不同的是，窗口左侧收缩的满足条件是 当S包含T的所有字符时。

代码实现：

 public String minWindow (String S, String T) {
        // write code here
        HashMap<Character, Integer> need, window;
        need = new HashMap<Character, Integer>();
        window = new HashMap<Character, Integer>();

        for(int i=0; i < T.length(); i++){
            char c = T.charAt(i);
            need.put(c,need.getOrDefault(c,0)+1);
        }

        int left = 0, right = 0;
        //包含目标T的字符数
        int valid = 0;

        //记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;


        //窗口不断往右移 
        while(right < S.length()){
            char c = S.charAt(right);

            //右移窗口
            right++;
            //进行窗口内数据更新
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c) == need.get(c))
                    valid++;
            }

            //判断左侧是否进行收缩
            while(valid == need.size()){
                //更新最小覆盖子串
                if(right - left < len){
                    start = left;
                    len = right - left;
                }

                char d = S.charAt(left);
                //左移窗口
                left++;

                //进行窗口内数据更新
                if(need.containsKey(d)) {
                    if(window.get(d) == need.get(d))
                        valid--;
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : S.substring(start,start+len);

    }