Subtask 1, 2

Đầu tiên, ta sẽ nối ~n~ xâu để nhận được một xâu ~S~ độ dài ~N~. Đến đây, ta sẽ thực hiện xây dựng xâu kết quả lần lượt: chọn ra ký tự đầu tiên, chọn ra ký tự thứ hai, ...

Với mỗi ký tự thứ ~i~, ta sẽ thử đặt lần lượt các ký tự từ 'a' tới 'z' xem có thoả mãn điều kiện bài toán hay không.

Subtask 3

Ta sẽ duy trì một ~dp~ ~(j, 0/1/2)~, là có thể tạo được ~i~ ký tự đầu tiên của xâu kết quả (~i - 1~ ký tự đã tính được từ trước + ký tự thử) hay không, ~dp~ ~(j, 0)~ là chưa lấy ký tự nào trên xâu ~s_{id(j)}~ với ~s_{id(j)}~ là xâu ban đầu mà chứa ký tự thứ ~j~, ~dp~ ~(j, 1)~ là đang lấy các ký tự trên ~s_{id(j)}~ và ~dp~ ~(j, 2)~ là đã hoàn thành việc lấy ký tự trên ~s_{id(j)}~.

Với ~c~ là ký tự thử và ~dp'~ là trạng thái ~dp~ trước đó, ta sẽ có:

• Nếu ~id_j~ ~≠~ ~id_{j - 1}~:
  • ~dp~ ~(i, 0)~ ~|=~ ~dp~ ~(i - 1, 0)~
  • ~dp~ ~(i, 1)~ ~|=~ ~dp'~ ~(i - 1, 1)~ và ~dp~ ~(i, 2)~ ~|=~ ~dp'~ ~(i - 1, 2)~ nếu ~c~ ~=~ ~S_i~.
• Ngược lại:
  • ~dp~ ~(i, 0)~ ~|=~ ~dp~ ~(i - 1, 0)~
  • ~dp~ ~(i, 2)~ ~|=~ ~dp~ ~(i - 1, 2)~
  • ~dp~ ~(i, 1)~ ~|=~ ~dp'~ ~(i - 1, 1)~ ~|~ ~dp'~ ~(i - 1, 0)~ và ~dp~ ~(i, 1)~ ~|=~ ~dp'~ ~(i - 1, 1)~ ~|~ ~dp'~ ~(i - 1, 0)~ nếu ~c~ ~=~ ~S_i~.

~c~ được coi là đặt vào được vị trí ~i~ nếu tồn tại ~j~ sao cho ~j ≤ N - (k - i)~ và ~k - i + 1 ≥ n - id_j~ và ~dp~ ~(j, 2)~ ~=~ ~1~.

Độ phức tạp: ~Ο~ ~(26 \times N^2)~.