同じ文字が最低d文字以上離れるように文字列を再配置するPythonプログラム

問題の概要

空でない文字列 str と整数 k が与えられたとき、同じ文字同士が互いに少なくとも距離 k 以上離れるように文字列を並べ替えることを考えます。

入力文字列はすべて小文字アルファベットで構成されているものとします。条件を満たす並べ替えが不可能な場合は、空文字列 "" を返します。

例1

str = "tutorialspoint", k = 3

答え: "tiotiotalnprsu"

どの文字も、同じ文字との間に少なくとも3文字以上の距離が保たれています。

str = "aabbcc", k = 3

答え: "abcabc"

同じ文字が最低3文字分の間隔を空けて配置されています。

例2

str = "aaabc", k = 3

答え: ""

「a」が3つある一方で文字列全体の長さが5文字しかないため、同じ文字を3文字以上離して配置することができません。このような場合は並べ替え不可能として、空文字列を返します。

例3

str = "aaadbbcc", k = 2

答え: "abacabcd"

別の有効な解答: "abcabcda"

同じ文字同士が少なくとも2文字以上の距離を保っています。

アルゴリズムの考え方

この問題は、貪欲法(グリーディ法)と最大ヒープ(max heap)を組み合わせることで効率的に解くことができます。基本的な流れは以下のとおりです。

1. 各文字の出現回数を集計する。
2. 最大ヒープを使い、出現回数の多い文字から順に取り出す。
3. 取り出した文字を、まだ埋まっていない最も手前の位置から始めて、d間隔ごと(p、p+d、p+2d、…)に順番に配置していく。
4. 配置位置が文字列の範囲を超えてしまった場合は、条件を満たす並べ替えが存在しないと判断できる。

出現回数の多い文字を優先的に早い段階で配置することで、残りの文字のためのスペースが確保されやすくなり、条件を満たす解を見つけやすくなります。

Pythonでの実装例

MAX = 128

# 文字とその出現頻度を保持するクラス
class charFreq(object):
    def __init__(self, char, freq):
        self.c = char   # 文字
        self.f = freq   # 出現頻度

# 2つのcharFreq要素を入れ替えるユーティリティ関数
def swap(x, y):
    return y, x

# 文字列をリストに変換するユーティリティ関数
def toList(string):
    t = []
    for x in string:
        t.append(x)
    return t

# リストを文字列に戻すユーティリティ関数
def toString(l):
    return ''.join(l)

# ヒープ内のノード freq[i] を対象にmaxヒープ化する
def maxHeapify(freq, i, heap_size):
    l = i * 2 + 1
    r = i * 2 + 2
    largest = i
    if l < heap_size and freq[l].f > freq[i].f:
        largest = l
    if r < heap_size and freq[r].f > freq[largest].f:
        largest = r
    if largest != i:
        freq[i], freq[largest] = swap(freq[i], freq[largest])
        maxHeapify(freq, largest, heap_size)

# 配列 freq[] を最大ヒープに変換する
def buildHeap(freq, n):
    i = (n - 1) // 2
    while i >= 0:
        maxHeapify(freq, i, n)
        i -= 1

# 最大ヒープの根(最大の要素)を取り出す
def extractMax(freq, heap_size):
    root = freq[0]
    if heap_size > 1:
        freq[0] = freq[heap_size - 1]
        maxHeapify(freq, 0, heap_size - 1)
    return root

# 同じ文字同士が d 以上の距離になるように並べ替える本体
def rearrange(string, d):
    n = len(string)

    # 全文字とその出現頻度を格納する配列を用意
    freq = []
    for _ in range(MAX):
        freq.append(charFreq(0, 0))

    m = 0  # 異なる文字の種類数

    # 入力文字列を走査して各文字の出現頻度を記録
    for i in range(n):
        x = ord(string[i])
        if freq[x].c == 0:      # 初めて出現した文字ならカウント
            freq[x].c = chr(x)
            m += 1
        freq[x].f += 1
        string[i] = '\0'        # 元の位置を空きマークにする

    # 出現頻度に基づいて最大ヒープを構築
    buildHeap(freq, MAX)

    # 文字の種類数だけ取り出し、d間隔の制約付きで配置
    for i in range(m):
        x = extractMax(freq, MAX - i)

        # 配置可能な最初の位置を探す
        p = i
        while string[p] != '\0':
            p += 1

        # p, p+d, p+2d, ... の位置に文字を配置
        for k in range(x.f):
            # インデックスが範囲外なら並べ替え不可
            if p + d * k >= n:
                print("It is not possible to rearrange the string.")
                return ""
            string[p + d * k] = x.c

    return toString(string)

string = "tutorialspoint"
print(rearrange(toList(string), 3))

実行結果

tiotiotalnprsu

計算量とまとめ

文字数を n とすると、最大ヒープの構築に O(n)、以降の文字の抽出と配置全体でおよそ O(n log n) の計算時間がかかります。頻度の高い文字から優先的に間隔を空けて配置する貪欲戦略により、同じ文字が指定距離以上離れた文字列を効率的に生成できます。並べ替えが不可能なケース(特定の文字の出現回数が多すぎる場合など)も、配置位置が範囲外になった時点で検知して空文字列を返す仕組みになっています。