Chương trình tìm độ dài chuỗi ghép nối ký tự duy nhất tối đa trong Python

Cho danh sách chuỗi words. Cần tìm độ dài lớn nhất của chuỗi được tạo bằng cách ghép nối một dãy con của words sao cho mỗi ký tự trong chuỗi kết quả chỉ xuất hiện một lần (không trùng lặp).

Ví dụ

Đầu vào: words = ["xyz", "xyw", "wab", "cde"]

Không thể chọn từ nào vì chúng chứa ký tự trùng lặp (x, y, w lặp lại). Kết quả: 9 (chọn "xyz" + "wab" + "cde" → "xyzwabcde" độ dài 9).

Thuật toán (Backtracking / DFS)

1. Hàm helper is_unique(s) kiểm tra chuỗi có toàn ký tự duy nhất không.
2. Hàm đệ quy recur(i, current):
   • Nếu i == len(words): cập nhật ans = max(ans, len(current)).
   • Bỏ qua từ words[i]: gọi recur(i+1, current).
   • Nếu words[i] có ký tự duy nhất VÀ current + words[i] cũng duy nhất: gọi recur(i+1, current + words[i]).
3. Khởi tạo ans = 0, gọi recur(0, ""), trả về ans.

Triển khai Python

class Solution:
    def solve(self, words):
        ans = 0
        
        def is_unique(s):
            return len(set(s)) == len(s)
        
        def recur(i=0, cur=""):
            nonlocal ans
            if i == len(words):
                ans = max(ans, len(cur))
                return
            # Không chọn words[i]
            recur(i + 1, cur)
            # Chọn words[i] nếu hợp lệ
            if is_unique(words[i]) and is_unique(cur + words[i]):
                recur(i + 1, cur + words[i])
        
        recur()
        return ans

# Test
ob = Solution()
print(ob.solve(["xyz", "xyw", "wab", "cde"]))  # Output: 9

Độ phức tạp

• Thời gian: O(2ⁿ × L) với n số từ, L độ dài trung bình.
• Không gian: O(L) cho stack đệ quy.

Lưu ý: Có thể tối ưu bằng bitmask để biểu diễn tập ký tự.