Pythonで部分文字列を並べ替えて回文にできるか判定する方法

問題概要

文字列 s が与えられ、その部分文字列に対して複数のクエリを処理することを考えます。各クエリ queries[i] は [left, right, k] の3つの要素で構成されており、部分文字列 s[left]〜s[right] を自由に並べ替えたうえで、最大 k 個までの文字を任意の小文字アルファベットに置き換えることができます。これらの操作を施した結果、部分文字列が回文にできる場合は true、できない場合は false がクエリの結果となります。最終的に、i 番目のクエリ queries[i] の結果が answer[i] となる配列 answer[] を求めます。

例として、入力が「abcda」で、queries が [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] の場合、出力は [true, false, false, true, true] となります。

解法の考え方

回文の性質を利用すると、この問題は効率的に解けます。並べ替えが許されているため、同じ文字同士は左右対称の位置に配置でき、実際に置換が必要なのは「ペアになれない文字」、つまり区間内で奇数回出現する文字だけです。具体的には、区間内で奇数回出現する文字の種類数を one とすると、必要な置換回数は one ÷ 2（切り捨て）となり、これが k 以下であれば回文が成立します。

また、クエリごとに毎回出現回数を数えるのは非効率なため、累積和（プレフィックスサム）による dp テーブルを事前に構築します。dp[i][j] は「先頭から i 文字目までに文字 j が出現した回数」を表し、任意の区間 [l, r] 内での出現回数は dp[r][j] − dp[l−1][j] で即座に計算できます。

解法の手順

• solve メソッドを定義します。引数は dp 行列と q で、次のように動作します。
• l := q[0]、r := q[1]、k := q[2] とし、l と r をそれぞれ 1 増やし、one := 0 で初期化します。
• i を 0 から 25 まで繰り返し処理します。
  • one := one + (dp[r, i] − dp[l − 1, i]) mod 2 とします。
• one / 2 の整数除算の結果が k 以下であれば true を返し、そうでなければ false を返します。
• makeDP() メソッドも定義します。引数は dp 行列と s で、次のように動作します。
• i を 0 から s の長さまで繰り返します。
  • j を 0 から 25 まで繰り返します。
    • dp[i, j] := dp[i − 1, j] とします。
  • dp[i, ASCII(s[i]) − ASCII('a')] を 1 増やします。
• メインメソッドは以下のように実装します。
• n := 文字列 s のサイズとし、s := " " + s とします。
• dp := (n + 1) × 26 の行列を用意し、すべて 0 で初期化します。
• makeDP(dp, s) を呼び出します。
• res := クエリ数と同じ長さの配列を用意し、false で初期化します。
• i を 0 から q の長さ − 1 まで繰り返します。
  • res[i] := solve(dp, q[i]) とします。
• res を返します。

実装例（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]