Pythonで3つの条件のいずれかを満たすために変更する文字数を最小化するプログラム

問題の概要

小文字アルファベットのみで構成された2つの文字列 s と t が与えられます。1回の操作では、s または t 内の任意の1文字を、任意の小文字に変更することができます。目標は、以下の3つの条件のうちいずれか1つを満たすことです。

• s 内のすべての文字が、t 内のすべての文字よりもアルファベット順で厳密に小さい。
• t 内のすべての文字が、s 内のすべての文字よりもアルファベット順で厳密に小さい。
• s と t の両方が、それぞれ1種類の同一文字のみで構成されている。

この状態を達成するために必要な最小操作回数を求めます。

入力例と考え方

例えば、入力が s = "sts"、t = "uss" の場合、出力は 2 になります。それぞれの条件を満たす方法は次の通りです。

• 条件1: 2回の操作で t を "uuu" に変更すると、s 内のすべての文字(sts)が t 内のすべての文字(uuu)より小さくなります。
• 条件2: 3回の操作で s を "ttt" に、t を "sss" に変更すると、t 内のすべての文字が s 内のすべての文字より小さくなります。
• 条件3: 2回の操作で s を "sss" に、t を "sss" に変更すると、両方の文字列が1種類の文字のみで構成されます。

この中で最も操作回数が少ないのは、条件1または条件3を満たす「2回の操作」です。

解法のアプローチ

この問題は、各文字の出現頻度を集計しながら、アルファベット順に境界を走査することで効率的に解けます。各変数の役割は次の通りです。

• counter_s / counter_t: s・t 内の各文字の出現頻度を保持するマップ。
• unique: 条件3(両方を同じ1文字に揃える)に必要な操作回数。各文字 c について「全体の長さ − 両文字列内の c の出現数」の最小値を求めます。
• less_s: 条件1(s のすべての文字を t より小さくする)に必要な操作回数。
• less_t: 条件2(t のすべての文字を s より小さくする)に必要な操作回数。
• accu_s / accu_t: これまで走査した文字についての累積出現数。

文字 c を 'b' 以降に走査する際、それまでに累積した文字(= c 未満の文字)を境界として扱うことで、「s 側は境界未満の文字に揃え、t 側は境界以上の文字に揃える」場合のコストを計算できます。具体的には、len(s) − accu_s + accu_t(s 内の境界以上の文字を変更し、t 内の境界未満の文字を変更)が条件1のコストに対応します。条件2はその逆です。

アルゴリズムの手順

• counter_s := s の各文字の出現頻度マップを作成
• counter_t := t の各文字の出現頻度マップを作成
• less_s := 無限大、less_t := 無限大、unique := 無限大 で初期化
• accu_s := 0、accu_t := 0 で初期化
• 小文字アルファベットの各文字 c について以下を繰り返す:
  • unique := min(unique, len(s) + len(t) − counter_s[c] − counter_t[c])
  • c が 'a' より大きい場合:
    • less_s := min(less_s, len(s) − accu_s + accu_t)
    • less_t := min(less_t, len(t) − accu_t + accu_s)
  • accu_s := accu_s + counter_s[c]
  • accu_t := accu_t + counter_t[c]
• min(less_s, less_t, unique) を返す

実装例

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

from collections import Counter
import string

def solve(s, t):
    counter_s = Counter(s)
    counter_t = Counter(t)
    less_s, less_t, unique = float('inf'), float('inf'), float('inf')
    accu_s, accu_t = 0, 0
    for c in string.ascii_lowercase:
        # 条件3: 両方の文字列を1種類の文字 c に揃えるコスト
        unique = min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])
        if c > 'a':
            # 条件1: s の文字をすべて c 未満に、t の文字をすべて c 以上にするコスト
            less_s = min(less_s, len(s) - accu_s + accu_t)
            # 条件2: t の文字をすべて c 未満に、s の文字をすべて c 以上にするコスト
            less_t = min(less_t, len(t) - accu_t + accu_s)
        accu_s += counter_s[c]
        accu_t += counter_t[c]
    return min(less_s, less_t, unique)

s = "sts"
t = "uss"
print(solve(s, t))

入力

"sts", "uss"

出力

2

計算量

このアルゴリズムは、アルファベット26文字を一度だけ走査するため、時間計算量は O(n + 26)(n は两文字列の合計長)、空間計算量は O(1)(出現頻度マップは最大26種類)となります。文字列の長さが大きい場合でも高速に動作します。