Chương trình đếm số cách tách chuỗi tốt (good split) bằng Python

Cho chuỗi s. Tách tốt (good split) là chia s thành 2 chuỗi không rỗng p, q (p+q=s) sao cho số ký tự khác nhau trong p và q bằng nhau. Đếm số cách tách tốt.

Ví dụ: s="xxzxyx" → 2 cách: ("xxz","xyx") và ("xxzx","yx").

Thuật toán

• result=0, left=Counter(), right=Counter(s)
• Duyệt c trong s:
  • left[c] += 1; right[c] -= 1
  • Nếu right[c]==0: del right[c]
  • Nếu len(left) == len(right): result += 1
• Return result

Code Python

from collections import Counter

def solve(s):
    result = 0
    left, right = Counter(), Counter(s)
    for c in s:
        left[c] += 1
        right[c] -= 1
        if not right[c]:
            del right[c]
        if len(left) == len(right):
            result += 1
    return result

s = "xxzxyx"
print(solve(s))

Input

"xxzxyx"

Output

2