Cách 1: Trie

Nhận xét ban đầu: Ta sẽ thực hiện phép biến đổi chuỗi cho đến khi nào nó không còn biến đổi được nữa. Lưu ý rằng, sau mỗi phép biến đổi, chuỗi sẽ giảm đi 1 đơn vị. Do đó, số phép biến đổi sẽ không vượt quá độ dài chuỗi ban đầu.

Có một số trường hợp đặc biệt là chuỗi con có độ dài là \(1\) hoặc \(2\).

Trước tiên, với mỗi ký tự chữ cái, chúng ta sẽ tìm vị trí đầu tiên và cuối cùng xuất hiện của nó và lưu vào mảng \(a\). Sau đó, ta có thể sử dụng mảng \(a\) để xây dựng một cây \(Trie\) để lưu các chuỗi đang xét.

Sau đó, với mỗi truy vấn \((l, r)\), ta sẽ duyệt các ký tự của chuỗi con này từ trái sang phải. Với mỗi ký tự, ta sẽ đi tìm nó trong cây \(Trie\) và lưu lại kết quả tại đó. Nếu kết quả là \(Yes\), tức là chuỗi con này có thể biến thành một chuỗi rỗng, chúng ta sẽ dừng việc tìm kiếm và xuất ra kết quả ngay lập tức. Ngược lại, nếu kết quả là \(No\), tức là chuỗi con này không thể biến thành một chuỗi rỗng, ta tiếp tục duyệt các ký tự tiếp theo.

Một số ý tưởng cải tiến:

Để tìm vị trí đầu tiên và cuối cùng của mỗi ký tự, ta có thể sử dụng kỹ thuật hai con trỏ để làm cho việc này chỉ mất \(O(n)\).
Để tìm chuỗi con trong cây \(Trie\), ta có thể sử dụng một mảng hai chiều \(t\), trong đó \(t_{i,j}\) sẽ lưu lại vị trí đầu tiên của ký tự \(j\) trong từ \(i\) trở đi. Cụ thể hơn, với mỗi nút của cây \(Trie\), ta sẽ lưu một mảng \(cnt\) chứa số lượng các ký tự xuất hiện tại nút đó. Sau đó, để tìm một chuỗi con trong cây \(Trie\), ta chỉ cần đi xuống theo các nút con của nút hiện tại mà phù hợp với các ký tự của chuỗi con cần tìm. Nếu ta không thể đi xuống bất kỳ một nút con nào, tức là chuỗi con không tồn tại trong cây.

Để lưu trữ cây \(Trie\), ta có thể sử dụng cấu trúc dữ liệu con trỏ hoặc mảng động. Trong trường hợp này, do tập ký tự chỉ gồm các chữ cái tiếng anh viết thường, nên ta có thể sử dụng mảng tĩnh để lưu trữ các con trỏ tới các nút con của một nút. Với mỗi nút của cây, ta lưu trữ một giá trị bool để đánh dấu xem nút đó có phải là một nút lá hay không. Nếu một nút là nút lá, thì nó đại diện cho một từ trong tập từ điển.

Để xây dựng cây \(Trie\) từ tập từ điển, ta sẽ chèn các từ của tập từ điển vào cây một cách tuần tự. Để chèn một từ vào cây, ta sẽ đi xuống từ gốc của cây theo các ký tự của từ đó và tạo ra các nút con mới nếu cần thiết. Khi đến cuối từ, ta đánh dấu nút hiện tại là nút lá để đại diện cho từ đó.

Sau khi xây dựng xong cây \(Trie\), ta có thể tìm kiếm các từ trong tập từ điển bằng cách đi xuống theo cây \(Trie\) theo các ký tự của từ đó. Nếu ta đến được một nút lá tại cuối từ, tức là từ đó tồn tại trong tập từ điển.

Trong bài toán này, ta cũng sử dụng cây \(Trie\) để lưu trữ các chuỗi con của chuỗi ban đầu và tìm kiếm các chuỗi con này trong cây \(Trie\) khi thực hiện các truy vấn.

Độ phức tạp của thuật toán này là \(O(n)\) với \(n\) là độ dài của chuỗi

Cách 2: DP + RMQ

Bài toán yêu cầu ta xét khả năng biến chuỗi con \(T\) được tạo thành từ \(S_l\) đến \(S_r\) trở thành chuỗi rỗng sau khi áp dụng các bước biến đổi như robot đã được đề cập. Nhìn vào bài toán ta có thể nhận thấy rằng nếu một kí tự bị xóa thì kí tự đứng ngay sau nó sẽ được cân nhắc xóa trong các lần xử lí tiếp theo, cụ thể nếu sau lần xử lí thứ \(i\) kí tự \(S_k\) bị xóa thì sau lần xử lí thứ \(i+1\) ta sẽ xét đến kí tự \(S_{k-1}\).

Một cách đơn giản nhưng cũng rất hiệu quả để xử lí bài toán này đó là ta có thể dùng tìm kiếm nhị phân trên các kí tự \(S_i\) để tìm vị trí \(S_{i+1}\) đầu tiên xuất hiện kí tự giống \(S_i\) (nếu có). Tìm kiếm này được thực hiện bằng cách sử dụng 2 mảng \(dp\) và \(rmq\) như sau:

\(dp[i][j]\) là vị trí đầu tiên \(S_{k} = j\) trong đoạn \([i, n]\) (nếu có). Lưu ý rằng với \(dp[i][j] = 1e9\) nghĩa là không có kí tự \(j\) nào xuất hiện trong đoạn \([i, n]\).
\(rmq[i][j]\) là giá trị nhỏ nhất mà ta có thể biến đổi kí tự \(S_i\) thành kí tự \(j\) (tức là \(change\) được đưa ra trong câu hỏi của đề bài).
Mảng \(dp\) có thể được tính bằng cách duyệt chuỗi từ trái sang phải và cập nhật giá trị cho mỗi kí tự trong chuỗi. Với mỗi kí tự \(S_i\) chúng ta chỉ cần gán \(dp[i][S_i] = i+1\). Sau đó ta sử dụng giá trị trong mảng \(dp\) để tìm vị trí \(S_{i+1}\) đầu tiên xuất hiện kí tự giống \(S_i\) thông qua tìm kiếm nhị phân.

Mảng \(rmq\) cũng có thể được tính bằng cách duyệt chuỗi từ trái sang phải. Với mỗi kí tự \(S_i\), nếu giá trị của \(S_{i+1}\) giống với \(S_i\) thì ta sẽ gán \(rmq[i][S_i] = rmq[i+1][S_i]\) (tức là giá trị nhỏ nhất của đoạn \(S_{i...j}\) sẽ bằng giá trị nhỏ nhất của đoạn \(S_{i+1...j}\).

Tuy nhiên, để tính giá trị nhỏ nhất của đoạn \(S_{i...j}\) trong trường hợp \(S_i \neq S_j\), ta có thể sử dụng một kỹ thuật khác là Sparse Table. Cụ thể, ta sẽ tính toán một bảng \(st[i][j]\), trong đó \(st[i][j]\) là giá trị nhỏ nhất của đoạn \(S_{i...i+2^j-1}\). Từ đó, để tính giá trị nhỏ nhất của đoạn \(S_{i...j}\), ta có thể tìm \(k\) sao cho \(2^k \leq j-i+1\) và tính giá trị nhỏ nhất của hai đoạn \(S_{i...i+2^k-1}\) và \(S_{j-2^k+1...j}\).

Cả hai kỹ thuật trên đều có độ phức tạp là \(O(n\log n)\) và đều cho phép truy vấn giá trị nhỏ nhất của một đoạn trong chuỗi \(S\) trong thời gian \(O(1)\).