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.

My approach was to process the string left to right and keep count of the number of sequences "^" and "^_" seen so far. When we see a "^", then we can form "^_^" if there is any "^_" subsequence before or keep it as an unmatched "^" to form a "^_" subsequence later.

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