可以从Python中的子字符串生成回文
假设我们有一个字符串s，我们必须对s的子字符串进行查询。对于每个查询查询[i]，它分为三个部分[left，right，k]，我们可以重新排列子字符串s[left]，...，s[right]，然后最多选择k个子字符串替换为任何小写英文字母。如果在上述操作之后子字符串可能是回文，则查询结果为true。否则为假。我们必须找到一个数组answer[]，其中answer[i]是第i个查询query[i]的结果。
例如，如果输入为“abcda”，则查询类似于[[3,3,0]，[1,2,0]，[0,3,1]，[0,3,2]，[0，4,1]]，则输出将为[true，false，false，true，true]
为了解决这个问题，我们将遵循以下步骤-
定义一个名为Solve的方法，它将采用dp矩阵和q。这将如下所示工作-
l：=q[0]，r：=q[1]，k：=q[2]，然后将l和r加1，一个：=0
当我在0到25的范围内
一个：=一个+（dp[r，i]–dp[l–1，i]）mod2
当整数除以1/2<=k时返回true，否则返回false
定义另一个名为的方法makeDP()，它将采用dp矩阵和s，其工作方式如下：
对于范围在0到s长度之间的i
dp[i，j]：=dp[i–1，j]
适用于0到25范围内的j
将dp[i，s[i]的ASCII–'a'的ASCII]增加1
主要方法将是-
n：=字符串s的大小，s：=“”连接s
dp：=阶（n+1）x26的矩阵，并用0填充
调用makeDP(dp,s)
res：=长度与q长度相同的数组，并用false填充
对于i，范围为0至q–1的长度
res[i]：=solve（dp，q[i]）
返回资源
示例(Python)
让我们看下面的实现以更好地理解-
class Solution(object):
def solve(self,dp,q):
l = q[0]
r = q[1]
k = q[2]
r+=1
l+=1
#arr = [ 0 for i in range(26)]
one = 0
for i in range(26):
one += (dp[r][i]-dp[l-1][i])%2
return one//2<=k
def make_dp(self,dp,s):
for i in range(1,len(s)):
for j in range(26):
dp[i][j] = dp[i-1][j]
dp[i][ord(s[i])-ord('a')]+=1
def canMakePaliQueries(self, s, q):
n = len(s)
s = " "+s
dp = [[0 for i in range(26)] for j in range(n+1)]
self.make_dp(dp,s)
res = [False for i in range(len(q))]
for i in range(len(q)):
res[i] = self.solve(dp,q[i])
return res
ob = Solution()print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))输入值
"abcda" [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出结果
[True, False, False, True, True]