Rút gọn chuỗi

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1900 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một xâu chỉ gồm hai loại kí tự a và b. Bạn có thể thực hiện phép rút gọn xâu như sau: thay thế một xâu con dạng a?a hoặc b?b thành ?, trong đó ? thể hiện cho một kí tự bất kì.

Yêu cầu: Tìm cách rút gọn xâu cho trước thành một xâu với độ dài nhỏ nhất có thể, chỉ ra độ dài đó.

Input

Gồm một dòng duy nhất ghi xâu ban đầu.

Output

Gồm một dòng duy nhất ghi độ dài nhỏ nhất của xâu sau khi rút gọn.

Constraints

Độ dài xâu ban đầu không quá \(300\).

Example

Test 1

Input

baaba

Output

Note

Xâu baaba có thể được rút gọn như sau:

Thay thế xâu con aba (dạng a?a) thành b: baaba \(\rightarrow\) bab.
Thay thế xâu con bab (dạng b?b) thành a: bab \(\rightarrow\) a.
Độ dài nhỏ nhất đạt được là \(1\).

Bình luận

Tải bình luận...

Không có bình luận nào.