Tìm số cặp () ít nhất để biến đổi chuỗi s

[bubabua (Huy Quang)]

Huyền vừa học được cách biến đổi ký tự như sau.

• Tất cả ký tự trong cặp dấu ()
  • Nếu là ký tự in hoa thì biến đổi thành ký tự in thường
  • Ngược lại nếu là ký tự in thường thì biến đổi thành ký tự in hoa.
  • Ví dụ "(abC)" sẽ biến đổi thành "ABc" .
• Các cặp dấu () có thể lồng nhau.
  • Ví dụ "(aB(cDe))" sẽ biến đổi thành "AbcDe".
    Vì "(aB(cDe))" -> "(aBCdE)" -> "AbcDe" .

Cho chuỗi s chỉ gồm các ký tự in hoa và in thường, Huyền muốn đặt một số cặp () vào chuỗi s để chuỗi s trở thành chuỗi chỉ có các ký tự in thường hoặc in hoa.

Hãy tìm và in ra số cặp () ít nhất có thể để Huyền biến đổi được chuỗi s theo yêu cầu của Huyền.

Ví dụ:

• Với s = "abC" , thì changeCharacter(s) = 1 .
  Giải thích:
  Có nhiều cách để biến đổi s thành chuỗi in thường hoặc in hoa như "(ab)C", "ab(C)", "ab(((C)))",... Nhưng cách ít nhất chỉ dùng 1 cặp () .

Ai giúp e bài này với ạ.

[SITUVN.gcd]

Trước mắt là thế này:

Tính số lượng nhóm các kí tự in HOA và in thường liên tiếp.
Nhóm nào ít hơn thì biến đổi nhóm đó.

AbcdEF

2 nhóm HOA (A và EF).
1 nhóm thường (bcd).
=> biến đổi 1 nhóm thường. 1 cặp ngoặc đơn.

AbCdEfG

4 nhóm HOA.
3 nhóm thường.
=> biến đổi 3 nhóm thường. 3 cặp ngoặc đơn.

Liệu có khả năng nào để kết hợp các cặp lồng nhau (không lồng liên tiếp) để tối thiểu hóa số lượng cặp ngoặc đơn không nhỉ?
Mong mọi người góp ý!

[rogp10]

Đưa về bài NOT một chuỗi nhị phân