파이썬에서 모든 부분 문자열의 아름다움의 합을 찾는 프로그램

<시간/>

문자열 s가 있다고 가정합니다. 우리는 모든 부분 문자열의 아름다움의 합을 찾아야 합니다. 문자열의 아름다움은 실제로 가장 자주 사용되는 문자와 가장 자주 사용되지 않는 문자 간의 빈도 차이입니다. 따라서 문자열이 "abaacc"이면 빈도는 3 - 1 =2입니다.

따라서 입력이 s ="xxyzy"와 같으면 아름다움이 0이 아닌 부분 문자열이 ["xxy","xxyz","xxyzy","xyzy","yzy"]이므로 출력은 5가 됩니다. 각각의 아름다움 값은 1입니다.

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

해상도:=0
범위 0에서 s - 1까지의 i에 대해 수행
- 범위 i+2에서 s - 1까지의 j에 대해 다음을 수행합니다.
  - c:=인덱스 i에서 j까지 s의 부분 문자열 빈도를 포함하는 맵
  - v:=c의 모든 주파수 값 목록
  - res :=res +(v의 최대값 - v의 최소값)
반환 해상도

예시

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

from collections import Counter

def solve(s):
   res=0
   for i in range(len(s)):
      for j in range(i+2,len(s)):
         c=Counter(s[i:j+1])
         v=c.values()
         res+=(max(v)-min(v))
   return res

s = "xxyzy"
print(solve(s))

입력

"xxyzy"