counting_valleys

Lịch trình leo núi của một người được ghi lại bởi một string s gồm các kí tự 'U' và 'D'. 'U' biểu hiện lên dốc 1 đơn vị độ cao, 'D' biểu hiện xuống dốc 1 đơn vị.

Một ngọn núi được xác định là một chuỗi các bước trên mực nước biển, bắt đầu bằng một bước lên tại mực nước biển, và kết thúc bằng một bước xuống mực nước biển.

Một thung lũng được xác định là một chuỗi các bước dưới mực nước biển, bắt đầu bằng một bước xuống tại mực nước biển, và kết thúc bằng một bước lên mực nước biển.

Ví dụ:

• Với s = "UDDDUDUU", thì ta có biểu diễn quá trình leo núi như sau:

Yêu cầu cho biết số thung lũng mà người đó đã đi qua?

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

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] string s
  2 <= len(s) <= 10^6
s.count('U') == s.count('D')

• [Đầu ra] Integer
  Số thung lũng người đó đi qua