Suppose we have a string s, we need to make queries for substrings of s. For each query [i] there are three parts [left, right, k], we can rearrange the substring s [left], & # 8230 ;, s [right] and then select up to k of them to replace with any lowercase English letter .
If the substring can be a palindrome after the operations mentioned above, the result of the query will be true. Otherwise, false. We have to find the array answer , where answer [i] is the result of the i-th query of queries [i].
For example, if the input is "abcda", the queries look like [[3,3,0], [1,2,0], [0,3,1], [0,3,2], [0, 4,1]], then the output will be [true, false, false, true, true]
To solve this problem:
Let`s take a look at the following implementation to better understand &
class Solution (object ): def solve (self, dp, q): l = q  r = q  k = q  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 & lt; = k return False 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): " "" : type s: str : type queries: List [List [int]] : rtype: List [bool ] "" " 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
"abcda" [[3,3,0], [1,2,0], [0,3,1], [0 , 3,2], [0, 4,1]]
[true, false, false, true, true]