+

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 [0], r: = q [1], k: = q [2], 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 [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 & 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 

    Input < / h2>
     "abcda" [[3,3,0], [1,2,0], [0,3,1], [0 , 3,2], [0, 4,1]] 

    Output

     [true, false, false, true, true] 



     

Get Solution for free from DataCamp guru