# 1. Tóm tắt đề bài Cho một mảng các xâu, tìm độ dài của xâu dài nhất *không chứa ký tự bị lặp* có thể tạo thành bằng cách *kết hợp mảng con* của mảng đã cho. Một *mảng con* là mảng có thể được tạo ra từ mảng đã cho bằng cách xoá một số hoặc không phần tử nào mà không thay đổi thứ tự của các phần tử còn lại. ### Giới hạn - $1 \le arr.length \le 16$ - $1 \le arr[i] \le 26$ - $arr[i]$ chỉ chứa các ký tự chữ in thường # 2. Tóm tắt lời giải **Độ phức tạp dự tính: $O(2^n)$** Với giới hạn được đưa và yêu cầu đề bài, sử dụng Backtracking để tìm ra tất cả các mảng xâu con hợp lệ và tìm ra max là một phương án phù hợp. Đối với việc kiểm tra ký tự bị lặp trong xâu, ta có thể sử dụng Bit Manipulation để thực hiện một cách hiệu quả hơn. # 3. Lời giải chi tiết *Lưu ý*: Với code lời giải Python, mình sẽ sử dụng các [toán tử trên set](https://docs.python.org/3/library/stdtypes.html#frozenset.union) có sẵn của ngôn ngữ. Đối với C++ và Java các bạn có thể sử dụng `bitset` hoặc một mảng `bool` dài `26` bit. *Các toán tử được sử dụng và bảng chân trị:* - AND `&`: Trả về `1` hay `True` khi và chỉ khi cả 2 bit đều là `1`, được sử dụng để xét khi ta merge 2 bitset vào với nhau có bit nào bị "chiếm chỗ" chưa (có bị trùng ký tự không). |A|B|Kết quả| |-|-|-------| |0|0|0 | |1|0|0 | |0|1|0 | |1|1|1 | - OR `|`: Trả về `1` hay `True` khi 1 trong 2 bit là `1`, dùng để merge 2 bitset lại với nhau. |A|B|Kết quả| |-|-|-------| |0|0|0 | |1|0|1 | |0|1|1 | |1|1|1 | - Set Difference `-`: Là một trong những toán tử trên set có sẵn của Python; `A - B` trả về set mới có những phần tử ở `A` nhưng không có ở `B` #### Cách 1: Iterative (tốn bộ nhớ mở rộng hơn) Ta tạo một danh sách `combi` để chứa tất cả các mảng con hợp lệ (khi kết hợp thành xâu không có ký tự bị lặp) có thể được tạo ra từ mảng ban đầu, mỗi mảng con được lưu lại dưới dạng một tập hợp dài 26 bit. Phần tử khởi tạo của `combi` sẽ là một mảng con rỗng (đại diện cho việc không chọn các xâu đứng trước). Với mỗi xâu trong `arr`, ta xét xem xâu có thể được thêm vào các mảng con tạo ra từ trước không trong `combi`, nếu có thì ta thêm mảng con mới vào danh sách. Cuối cùng ta tìm bitset nào trong `combi` có nhiều bit `1` nhất là đó là xâu có nhiều ký tự nhất. Để tối ưu hơn, trước khi thực hiện duyệt các mảng con hợp lệ, ta loại những xâu trong `arr` mà chính nó đã có ký tự bị lặp. Có thể thấy cách này dùng bộ nhớ mở rộng có cận trên là $O(26 \cdot 2^n) = O(2^n)$, đổi lại code theo cách này rất elegant và dễ nhìn. ```python= class Solution: def maxLength(self, arr: List[str]) -> int: valid = [] for s in arr: t = set(s) if len(t) == len(s): valid.append(t) # append sets for set operations later combi = [set()] for v in valid: for c in combi.copy(): if not c & v: combi.append(c | v) return max(len(s) for s in combi) ``` #### Cách 2: DFS Cách này gần hơn với Backtracking thông thường là ta sẽ hình dung bài toán như một cây quyết định, với mỗi xâu trong `arr` ta có thể chọn hoặc không chọn xâu đó vào trong mảng con trên nhánh hiện tại, và với một cây như vậy ta dùng DFS để duyệt qua tất cả các lựa chọn. Để tìm xâu max ta tạo biến `res` ở ngoài. Khi ta duyệt đến một lá, nghĩa là không thêm được xâu nào vào mảng con hiện tại nữa, ta cập nhật `res = max(res, len(curr_combi))`. **Code mẫu cách này tại [đây](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/submissions/1154229796?envType=daily-question&envId=2024-01-23).** ### Độ phức tạp thuật toán Thời gian: $O(2^n)$ Bộ nhớ mở rộng (tối ưu): $O(n)$ # 4. Kết luận & Gợi ý mở rộng Một bài có sự kết hợp thú vị giữa kỹ thuật Backtracking và các phép toán Bit. Những bạn vẫn chưa tự tin lắm với Backtracking có thể giải qua hoặc ôn lại những bài toán cơ bản dưới đây: [78. Subsets](https://leetcode.com/problems/subsets/) [17. Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/) [52. N-Queens II](https://leetcode.com/problems/n-queens-ii/)