Chương trình tìm một số cách tốt để chia một chuỗi bằng Python

Giả sử chúng ta có một chuỗi s. Bây giờ một phép chia được cho là một phép tách tốt khi chúng ta có thể chia s thành 2 chuỗi không rỗng p và q trong đó nối của nó bằng s và số chữ cái phân biệt trong p và q bằng nhau. Chúng ta phải tìm ra số lượng phân chia tốt mà chúng ta có thể thực hiện trong s.

Vì vậy, nếu đầu vào là s =​​"xxzxyx", thì đầu ra sẽ là 2 vì có nhiều cách tách nhưng nếu chúng ta chia như ("xxz", "xyx") hoặc ("xxzx", "yx") thì chúng tốt.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• kết quả:=0

• left:=mal trống để đếm tần suất của các mục

• right:=Đếm tần số xuất hiện của mỗi ký tự trong s

• đối với mỗi c trong s, thực hiện

  • left [c]:=left [c] + 1

  • right [c]:=right [c] - 1

  • nếu đúng [c] bằng 0 thì

    • loại bỏ bên phải [c]

  • nếu kích thước của bên trái giống với kích thước của bên phải, thì

    • kết quả:=kết quả + 1

• trả về kết quả

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

"xxzxyx"

Đầu ra

2