Hi everyone,

I saw this question on Quora about Problem E — Emoticons from Dhaka Preliminary Round 2015 (problemset). The statement is as follows:

Given a string S (|S| <= 10⁵) of characters '^' or '_', find the number of disjoint '^_^' subsequences. Disjoint means that we can't use the same character in 2 subsequences. For example, if S is ^^__^^ then the answer is 2. However, for S equal to _^^ the answer is 0.

I think the intended solution is a greedy algorithm, but I couldn't find a greedy approach that works in all cases. Any thoughts?

Sample input (number of tests <= 5000 but number of characters in a input file <= 2.1 * 10⁶)

7
_^^_^^_
^__^__^
______
^^__^^
^_^^__^
^_^_^^
^_^_^_^^^^_^_^

Sample output

1
1
0
2
2
2
4