Pythonで文字の頻度を一意にするために必要な最小限の削除をカウントするプログラム

文字列sがあるとすると、同じ頻度の2つの異なる文字がsにない場合、sは適切であると言われます。 sを適切な文字列にするために、削除する必要のある最小文字数を見つける必要があります。

したがって、入力がs ="ssstttuu"の場合、出力は2になります。これは、1つの't'を削除すると、3つの's'、2つの't'、および2つの'u'が存在するため、再度削除するためです。 1つは、「t」または「u」のいずれかで、それらを適切なものにします。

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

• val：=sの各文字の頻度を含む新しいマップ
• res：=0
• numlist：=valからすべての頻度値のリストを並べ替える
• 範囲0からnumlist-2のサイズのiの場合、実行
  • numlist [i]がゼロ以外で、numlist[i]がnumlist[i + 1]と同じである場合、
    • numlist [i]：=numlist [i]-1
    • res：=res + 1
    • k：=i-1
    • m：=i
    • numlist [m]がゼロ以外であり、numlist[m]がnumlist[k]と同じである場合、do
      • numlist [k]：=numlist [k]-1
      • k：=k-1
      • m：=m-1
      • res：=res + 1
• return res

例

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

from collections import Counter
def solve(s):
   val = Counter(s)
   res = 0
   numlist = sorted([i for i in val.values()])
   for i in range(len(numlist)-1):
      if numlist[i] and numlist[i] == numlist[i+1]:
         numlist[i] -= 1
         res += 1
         k = i-1
         m = i
         while numlist[m] and numlist[m] == numlist[k]:
            numlist[k] -= 1
            k -= 1
            m -= 1
            res += 1

   return res

s = "ssstttuu"
print(solve(s))

入力

"ssstttuu"

出力

2