[BOJ] 1522 문자열 교환

문제 링크

www.acmicpc.net/problem/1522

풀이

슬라이딩 윈도우 문제이다.
a의 개수를 길이로 하는 구간을 잡아서 모든 구간에 대해 탐색하며 해당 구간에 속하는 b의 개수의 최솟값을 찾으면 된다.

Python 3 코드

S = input()
a = S.count('a')

ans = len(S)
for i in range(a - 1, len(S)):
    ans = min(ans, S[i - a + 1:i + 1].count('b'))

for i in range(0, a - 1):
    ans = min(ans, (S[i - a + 1:] + S[:i + 1]).count('b'))

print(ans)