Pythonの3つの条件を満たすように最小文字を変更するプログラム

小文字のみの2つの文字列sとtがあるとします。 1つの操作で、sまたはtの任意の文字を任意の小文字に変更できます。次の3つの条件のいずれかを満たす必要があります-

• sのすべての文字は、アルファベットのtのすべての文字よりも厳密に小さくなっています。

• tのすべての文字は、アルファベットのsのすべての文字よりも厳密に小さくなっています。

• sとtはどちらも1つの異なる文字のみで構成されています。

結果を得るのに必要な最小限の操作数を見つける必要があります。

したがって、入力がs ="sts"、t ="uss"の場合、出力は2になります。

• 2回の操作でtを「uuu」に変更すると、sのすべての文字はtのすべての文字よりも小さくなります。

• 3回の操作でsを「ttt」に、tを「sss」に変更すると、tのすべての文字はsのすべての文字よりも小さくなります。

• 2つの操作でsを「sss」に、tを「sss」に変更すると、sとtは1つの異なる文字で構成されます。

ここでは、2つの操作（1つまたは3つ）で最善の方法が実行されました。

これを解決するには、次の手順に従います-

• counter_s：=sの各文字の頻度を保持するためのマップ
• counter_t：=各文字の頻度をtに保持するためのマップ
• less_s：=無限大、less_t：=無限大、一意：=無限大
• accu_s：=0、accu_t：=0
• 英語の小文字のcごとに、
  • unique：=一意の最小値および（sのサイズ+tのサイズ-counter_s[c]-counter_t [c]）
    • counter_t [c]）
  • cのASCIIが'a'のASCIIよりも大きい場合、
    • less_a：=最小のless_sおよび（sのサイズ-accu_s + accu_t）
    • less_b：=最小のless_tおよび（tのサイズ-accu_t + accu_s）
  • accu_s：=accu_s + counter_s [c]
  • accu_t：=accu_t + counter_t [c]
• 最小のless_s、less_t、uniqueを返す

例

理解を深めるために、次の実装を見てみましょう-

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:
      unique = min(unique, len(s) + len(t) - counter_s[c] - counter_t[c])
      if c > 'a':
         less_a = min(less_s, len(s) - accu_s + accu_t)
         less_b = 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