길이가 짝수인 소문자 문자열 s가 있다고 가정합니다. 모든 i에 대해 다음 세 가지 조건 중 하나가 충족되도록 업데이트해야 하는 최소 문자 수를 찾아야 합니다. 여기서 0 ≤ i
- s[i]> s[j]
- s[i]
- s[i] ==s[j]
따라서 입력이 s ="pppxxp"와 같으면 출력은 1이 됩니다. 왜냐하면 마지막 "p"를 "x"로 변경하면 s[i]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=s의 크기
- left :=s의 왼쪽 절반부터 각 문자의 빈도를 포함하는 사전
- right :=s의 오른쪽 절반에서 각 문자의 빈도를 포함하는 사전
- an :=n
- 영문 소문자의 각 문자 피벗에 대해 다음을 수행합니다.
- ans :=ans의 최소값 및 (n - 왼쪽[피벗] - 오른쪽[피벗])
- good :=왼쪽에 있는 각 c에 대해 (left[c] if c <=pivot )에 있는 모든 요소의 합
- good :=good + right에 있는 모든 요소의 합[c] if c> pivot
- ans :=ans 및 (n - 양호)의 최소값
- good :=왼쪽의 각 c에 대해 왼쪽[c]에 있는 모든 요소의 합계 if c> 피벗
- good :=good + 오른쪽에 있는 모든 요소의 합[c] if c <=피벗
- ans :=ans 및 (n - 양호)의 최소값
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import Counter from string import ascii_lowercase def solve(s): n = len(s) left = Counter(s[: n >> 1]) right = Counter(s[n >> 1 :]) ans = n for pivot in ascii_lowercase: ans = min(ans, n - left[pivot] - right[pivot]) good = sum(left[c] for c in left if c <= pivot) good += sum(right[c] for c in right if c > pivot) ans = min(ans, n - good) good = sum(left[c] for c in left if c > pivot) good += sum(right[c] for c in right if c <= pivot) ans = min(ans, n - good) return ans s = "pppxxp" print(solve(s))
입력
"pppxxp"
출력
1