changeCharacter2

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 ().

Đầu vào/Đầu ra:

• [Thời gian] 0.1s với C++, 0.6s với Java và C#, 0.8s với Python, Go và JavaScript.
• [Đầu vào] String 
  s.length ≤ 105.
• [Đầu ra] Integer.
  Số cặp () tối thiểu cần đặt vào s để chuỗi s trở thành chuỗi chỉ có các ký tự in thường hoặc in hoa.