一、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需要逆序，列需要顺序文章来源：https://www.toymoban.com/news/detail-825607.html
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))
文章来源地址https://www.toymoban.com/news/detail-825607.html
到了这里，关于最长子串和回文子串相关的算法题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
