Python에서 문자 빈도를 고유하게 만드는 데 필요한 최소 삭제 수를 계산하는 프로그램

<시간/>

문자열 s가 있다고 가정하고 s에 동일한 빈도를 갖는 두 개의 다른 문자가 없으면 s는 양호하다고 합니다. s를 좋은 문자열로 만들기 위해 삭제해야 하는 최소 문자 수를 찾아야 합니다.

따라서 입력이 s ="ssstttuu"와 같으면 출력은 2가 됩니다. 왜냐하면 하나의 't'를 삭제하면 3개의 '', 2개의 't' 및 2개의 'u'가 있고 다시 삭제하기 때문입니다. 'u' 또는 'u' 중 하나를 사용하여 좋게 만듭니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

val :=s의 각 문자의 빈도를 포함하는 새 지도
res :=0
numlist :=val의 모든 빈도 값 목록 정렬
0 범위에서 numlist -2 크기까지의 i에 대해
- numlist[i]가 0이 아니고 numlist[i]가 numlist[i+1]과 같으면
  - numlist[i] :=numlist[i] - 1
  - res :=res + 1
  - k :=i-1
  - m :=나는
  - numlist[m]이 0이 아니고 numlist[m]이 numlist[k]와 동일한 동안 do
    - numlist[k] :=numlist[k] - 1
    - k :=k - 1
    - m :=m - 1
    - res :=res + 1
반환 결과

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"