Chương trình tìm kích thước các phân đoạn chuỗi mỗi chữ cái chỉ xuất hiện một lần trong Python

Cho chuỗi chữ thường s. Phân đoạn s thành nhiều mảnh nhất có thể sao cho mỗi chữ cái chỉ xuất hiện trong tối đa 1 mảnh. Trả về danh sách độ dài các mảnh.

Ví dụ: s = "momoplaykae" → [4, 1, 1, 4, 1] (phân đoạn: ["momo", "p", "l", "ayka", "e"]).

Giải thuật (Stack + Đếm tần suất)

1. Đếm tần suất mỗi ký tự trong s.
2. Duyệt từng ký tự char:
   • Giảm count[char], tăng length.
   • Dùng stack theo dõi các ký tự "chưa đóng" (vẫn còn xuất hiện sau).
   • Khi count[char] == 0 và stack rỗng → cắt đoạn, lưu length, reset length = 0.

Ví dụ minh họa

from collections import Counter

class Solution:
    def solve(self, s):
        count = Counter(s)
        out = []
        stk = []
        length = 0
        for char in s:
            count[char] -= 1
            length += 1
            while count[char] != 0 or stk:
                if count[char] != 0:
                    stk.append(char)
                    break
                if stk and count[stk[-1]] == 0:
                    stk.pop()
                else:
                    break
            if not stk and count[char] == 0:
                out.append(length)
                length = 0
        return out

ob = Solution()
s = "momoplaykae"
print(ob.solve(s))  # Output: [4, 1, 1, 4, 1]

Đầu vào / Đầu ra

Input: "momoplaykae"

Output: [4, 1, 1, 4, 1]