Chương trình tách chuỗi thành số lượng lớn nhất chuỗi con duy nhất trong Python

Cho chuỗi s. Tách thành các chuỗi con không rỗng duy nhất (không trùng lặp) sao cho số lượng chuỗi con tối đa.

Ví dụ: s="pqpqrrr" → 5. Tách: ['p','q','pq','r','rr']. Không được tách ['p','q','p','q','r','rr'] vì 'p','q' trùng.

Giải thuật (DFS + Backtracking)

1. DFS với tham số: chuỗi còn lại s, set path các chuỗi con đã dùng.
2. Nếu s rỗng: cập nhật res = max(res, len(path)).
3. Thử mọi độ dài tiền tố i từ 1..len(s):
   • x = s[:i].
   • Nếu x chưa trong path: đệ quy dfs(s[i:], path ∪ {x}).

Ví dụ minh họa

def solve(s):
    res = [0]
    def dfs(s, path=set()):
        if not s:
            res[0] = max(res[0], len(path))
            return
        for i in range(1, len(s) + 1):
            x = s[:i]
            if x not in path:
                dfs(s[i:], path | {x})
    dfs(s)
    return res[0]

s = "pqpqrrr"
print(solve(s))

Đầu vào

"pqpqrrr"

Đầu ra

5