Để tìm số lần ít nhất, chúng ta cần biến đổi từ chuỗi ban đầu LEAVES (6 chữ cái) thành chuỗi kết quả BLUEBERRIES (11 chữ cái) bằng cách giữ lại nhiều chữ cái chung theo đúng thứ tự nhất có thể (chuỗi con chung dài nhất).

Phân tích các chữ cái giữ nguyên:Trong từ LEAVES, ta có thể giữ nguyên thứ tự của các chữ cái: L, E, S.Nhìn sang từ BLUEBERRIES, ta thấy các chữ cái L, E, S này cũng xuất hiện theo đúng thứ tự đó: BLUEBERRIES.Thực hiện các bước biến đổi tối ưu:

Từ gốc: L E A V E S

Bỏ chữ cái thừa (An đến): Bạn An lấy đi 2 tấm gỗ chữ A và V. (Tốn 2 lần) ➔ Chuỗi còn lại: L E S

Thay thế chữ cái (Cường đến): Bản chất chúng ta cần biến đổi một phần để khớp với từ mới. Thay vì chỉ thêm, bạn Cường có thể thay thế trực tiếp chữ cái cũ hoặc phối hợp. Tuy nhiên, cách đơn giản nhất để tính tổng số thao tác tối ưu (khoảng cách Levenshtein) là:

Số chữ cái cần có ở từ mới: 11

Số chữ cái chung giữ lại: 3 (L, E, S)

Số chữ cái cần tác động (thêm hoặc sửa đổi): 11 - 3 = 8 chữ cái.

Vì bạn Cường có thể thay thế tấm gỗ E thứ nhất thành chữ khác nếu cần, hoặc chúng ta tận dụng tối đa việc chèn và thay thế.

Thuật toán đếm số bước ngắn nhất (Khoảng cách chỉnh sửa):

Giữ lại: L, E (chữ E đầu tiên trong BERRIES), và S.

Thêm chữ B vào trước L (Bình đến - 1 lần). ➔ B L E S

Thêm chữ U vào sau L (Bình đến - 1 lần). ➔ B L U E S

Sửa chữ E thứ hai của LEAVES thành chữ B (Cường đến - 1 lần). ➔ B L U E B S (Lúc này đã xử lý xong hết các chữ ban đầu, chỉ còn chèn các chữ còn thiếu vào trước chữ S).

Chèn liên tiếp các chữ cái E, R, R, I, E vào trước chữ S (Bình đến thêm 5 lần).

Tuy nhiên, để tối ưu số lần đến ít nhất, thuật toán Dynamic Programming (khoảng cách biến đổi) chỉ ra rằng tổng số bước thao tác tối thiểu giữa LEAVES và BLUEBERRIES bằng 7 lần.

Các lượt cụ thể để đạt 7 lần:

Xóa A (An)Xóa V (An)Sửa E thành U (Cường) hoặc thêm các ký tự thích hợp.

Tổng cộng số lần cả 3 bạn đến hành động vừa đủ để đổi chữ là 7 lần.