最长子串和回文子串相关的算法题解

在这里插入图片描述

这里写目录标题

一、3. 无重复字符的最长子串
二、5. 最长回文子串
三、647. 回文子串
四、516. 最长回文子序列

一、3. 无重复字符的最长子串

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

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

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

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

思路：
用滑动窗口的思想做

class Solution:
    def lengsubstring(self,s):
        arr=[]
        res= 0
        for i in s:
            while i in arr:
                arr.pop(0)
            arr.append(i)
            res=max(res,len(arr))
        return res

二、5. 最长回文子串

中等
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

思路：动态规划
判断所有字串是否为回文字串，选出最长的。
一：状态定义：
db[i][j]表示s[i:j+1]是否为回文子串，（这里+1是为了构造闭区间）
二：状态转移方程
1、当前ij状态
头尾必须相等（s[i]==s[j]）==>过去ij状态：去掉头尾之后还是一个回文（dp[i+1][j-1] is True）
2、边界条件
a、只要是找过去i、j状态的时候，就会涉及边界条件（即超出边界情况处理）：
边界当s[i] == s[j] 且 j-1-(i+1) <=0 ==> 即j-i<=2，一定是回文串
b、当 i==j时，指一个字符，一定是回文串
三、输出内容
db[i][j]为截取的字串，每次发现新回文都比较一下j-i+1，更新起始位置i与最大的长度

class S:
    def longest(self,s):
        n=len(s)
        if n<2:
            return s
        dp=[[False] * n for _ in range(n)]
        max_len=1
        index=0
        for i in range(n):
            dp[i][i]=True
        for j in range(1,n):
            for i in range(j):
                if s[i] == s[j]:
                    if j - i <= 2:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                if dp[i][j] ==True:
                    cur = j - i +1
                    if cur >max_len:
                        max_len=cur
                        index =i
        return s[index:index+max_len]

r=S()
s = "babad"
print(r.longest(s))

三、647. 回文子串

中等
给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。
回文字符串是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

思路：动态规划
dp[i][j]:表示区间范围[i,j](注意左闭右闭)的字串是否为回文子串，如果是db[i][j]为True，否则为False
转移逻辑：
当s[i]与s[j]不相等，dp[i][j]一定为False
当s[i]与s[j]相等时，分3中情况
1、下标i与下标j相同，同一个字符a，一定是回文串
2、下标i与下标j相差1，例如aa，一定是回文串
3、下标i与下标j相差大于1，例如cabac，此时s[i]与s[j]相等
需要查看i到j区间是不是回文子串就看aba是不是回文就可以，那么aba的区间就是i+1，j-1区间
这个区间是不是回文串就看dp[i+1][j-1]是否为True

class Solution1:
    def countSubString(self, s):
        # 二维数组 i 代表行，j代表列
        n = len(s)
        result = 0
        dp = [[False] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 1 or dp[i + 1][j - 1]:
                        dp[i][j] = True
                        result += 1
        return result


r = Solution1()
s = "aaa"
print(r.countSubString(s))

四、516. 最长回文子序列

中等
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

思路：动态规划
dp[i][j]从i到j位置的子序列的最大回文长度
dp[i][j]=1
if s[i]==s[j],dp[i][j]=dp[i+1][j-1]+2
else dp[i][j]=max(dp[i+1][j],dp[i][j-1])
dp[i][j]和他左下角，坐标、下面，三个dp值相关，所以行循环i需要逆序，列需要顺序

class Solution2:
    def longest(self,s):
        n=len(s)
        dp=[[0]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            dp[i][i]= 1
            for j in range(i+1,n):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])
        return dp[0][n-1]


res=Solution2()
s = "bbbab"
print(res.longest(s))