Pythonで部分文字列を辞書順に連結した文字列のk番目の文字を効率的に求める方法

文字列 input_str が与えられたとします。この文字列から作れるすべての部分文字列を求め、それらを辞書順（lexicographical order）に並べたうえで一つずつ連結し、新しい文字列を作成します。さらに整数 k も与えられるため、連結後の文字列におけるインデックス k の位置にある文字を返すことが課題です。

例えば、input_str = 'pqrs'、k = 6 という入力の場合、出力は「p」になります。

入力文字列から得られる部分文字列を辞書順に並べると、p, pq, pqr, pqrs, q, qr, qrs, r, rs, s となります。

これらをすべて連結すると「ppqpqrpqrsqqrqrsrrss」という文字列になります。インデックスは0始まりで数えるため、位置6にある文字は「p」です。

解法のアプローチ

すべての部分文字列を実際に生成して連結すると、文字列が長い場合に膨大なメモリと時間が必要になります。そこで、スタックを活用して必要な文字だけを効率よく特定する手法を用います。手順は以下の通りです。

• stk_list を、空文字列と input_str の全インデックスのリストを持つタプルで初期化する
• stk_list が空になるまで、以下の処理を繰り返す
  • stk_list から末尾のタプルを取り出し、pre（接頭辞）と temp（インデックスのリスト）に分解する
  • k が pre の長さより小さい場合、pre[k] を答えとして返す
  • k から pre の長さを減算する
  • temp 内の各インデックス i に対して、input_str[i] と次のインデックス i+1 のペアを作成し、降順にソートする
  • 同じ文字ごとにグループ化し、(pre + 文字, 次のインデックスのリスト) を stk_list に追加する
• 該当する文字が見つからなければ null を返す

この方法では、部分文字列を明示的に連結することなく、辞書順の並びを考慮しながら目的のインデックスへ段階的に近づいていくため、計算量を大幅に抑えられます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(input_str, k):
   stk_list = [("",list(range(len(input_str))))]
   while stk_list:
      pre, temp = stk_list.pop()
      if k < len(pre):
         return pre[k]
      k -= len(pre)
      input_sorted = sorted([(input_str[i],i+1) for i in temp if i < len(input_str)], reverse=True)
      i = 0
      while i < len(input_sorted):
         val = input_sorted[i][0]
         temp1 = [input_sorted[i][1]]
         j = i + 1
         while j < len(input_sorted) and input_sorted[j][0]== val:
            temp1.append(input_sorted[j][1])
            j += 1
         stk_list.append((pre+val, temp1))
         i = j
   return None

print(solve('pqrs', 6))

入力

'pqrs', 6

出力

p