Dễ dàng quan sát được tất cả chữ cái trong chuỗi cuối cùng thu được đều bằng nhau. Nếu chúng không bằng nhau, ta vẫn có thể gộp hai chữ cái khác nhau thành chữ cái thứ ba để thu được chuỗi ngắn hơn.

Đầu tiên để giải quyết bài toán này, ta cần giải quyết một bài toán con: "Cho một chuỗi liệu có thể rút gọn chuỗi con về một chữ cái ~ch~ duy nhất."

Xét một chuỗi con bắt đầu tại vị trí ~st~ và kết thúc ở vị trí ~ed~. Để kiểm tra được liệu có thể rút gọn chuỗi con đó thành một chữ cái duy nhất ~ch~, ta có thể dùng qui hoạch động:

• Nếu ~st = ed~ thì chỉ cần kiểm tra chữ cái ở vị trí ~ed~ của chuỗi có bằng ~ch~ không.
• Nếu không thì kiểm tra liệu có một vị trí ~k ≥ st~ và ~k < ed~ mà có thể rút gọn chuỗi con ~[st,k]~ về một chữ cái ~u~ và chuỗi con ~[k +1,ed]~ về một chữ cái ~v~ hay không (~v~ và ~u~ là hai chữ cái khác với ~ch~).

Quay lại với cách giải bài toán này, đặt ~dp[ch][i]~ là chuỗi ngắn nhất có thể sau khi rút gọn tiền tố kết thúc tại ~i~ và chỉ chứa các chữ cái ~ch~.Ta có thể dễ dàng nhận thấy nếu chuỗi được cho có độ dài là ~n~ thì kết quả của bài toán sẽ là ~max(dp[a][n], dp[b][n], dp[c][n])~. Để tìm ~dp[ch][i]~, với tất cả giá trị ~j ≤ i~, kiểm tra liệu có thể rút gọn chuỗi con ~[j,i]~ về một chữ cái ~ch~ không (áp dụng bài toán con trên). Với tất cả vị trí ~j~ có thể, ~dp[ch][i]=min(dp[ch][j−1]+1)~.

Độ phức tạp: ~O(n^3)~.