두 개의 문자 A와 B로 구성된 문자열 s가 있다고 가정하고 Bs가 모두 발생하기 전에 As가 모두 발생하도록 하려면 s에서 삭제해야 하는 최소 문자 수를 찾아야 합니다.
따라서 입력이 S ="AABABAB"와 같으면 출력은 1이 됩니다. AABBB를 얻기 위해 마지막 A를 제거할 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
a_right :=s에서 "A"가 발생한 횟수
-
b_left :=0
-
as :=a_right
-
s의 각 인덱스 i와 문자 c에 대해
-
c가 "A"와 같으면
-
a_right :=a_right - 1
-
-
그렇지 않으면
-
b_left :=b_left + 1
-
-
ans :=ans 및 a_right + b_left의 최소값
-
-
반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
class Solution:
def solve(self, s):
a_right = s.count("A")
b_left = 0
ans = a_right
for i, c in enumerate(s):
if c == "A":
a_right -= 1
else:
b_left += 1
ans = min(ans, a_right + b_left)
return ans
ob = Solution()
S = "AABAABB"
print(ob.solve(S)) 입력
"AABAABB"
출력
1