  # Python substring palindrome 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:

• Define a method called decide this will take the matrix dp, and q. This will work like below &
• l: = q , r: = q , k: = q , then increase l and r by 1, one: = 0
• for me ranging from 0 to 25
• one: = one + (dp [r, i] &dp [l &1, i]) mod 2
• return true when integer division of one / 2 & lt; = k, otherwise false
• Define another a method named makeDP (), it will take a matrix of dp and s, this will work like below:
• for me ranges from 0 to length with
• for j in the range 0 to 25
• dp [i, j]: = dp [i &1, j]
• increase dp [i, ASCII of s [i] &ASCII of " a "] by 1
• The main method will be like &
• n: = line size s , s: = "" concatenate s
• dp: = matrix of order (n + 1) x 26 and fill it with 0
• call makeDP (dp, s)
• < li> res: = array of size equal to length q and fill it with false
• for i ranging from 0 to length q &1
• res [i]: = solve (dp, q [i])
• return Res
• ## Example

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 `

## Output

` [true, false, false, true, true] `