Hi everyone,↵
↵
I saw [this question](https://www.quora.com/How-do-I-approach-Problem-E-EMOTICONS-in-this-problem-set-This-problem-set-is-of-ACM-ICPC-Dhaka-Regionals-2015-preliminary) on Quora about Problem E — Emoticons from Dhaka Preliminary Round 2015 ([problemset](https://www.dropbox.com/sh/27ziov8qdk06cmw/AABfHiKjqsIi1Ac9xwnpf5tQa/icpc_dpr_2015_problem_set.pdf?dl=0)). The statement is as follows:↵
↵
Given a string S (|S| <= $10^5$) 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^6$)↵
↵
~~~~~↵
7↵
_^^_^^_↵
^__^__^↵
______↵
^^__^^↵
^_^^__^↵
^_^_^^↵
^_^_^_^^^^_^_^↵
~~~~~↵
↵
**Sample output**↵
↵
~~~~~↵
1↵
1↵
0↵
2↵
2↵
2↵
4↵
~~~~~↵
↵
↵
I saw [this question](https://www.quora.com/How-do-I-approach-Problem-E-EMOTICONS-in-this-problem-set-This-problem-set-is-of-ACM-ICPC-Dhaka-Regionals-2015-preliminary) on Quora about Problem E — Emoticons from Dhaka Preliminary Round 2015 ([problemset](https://www.dropbox.com/sh/27ziov8qdk06cmw/AABfHiKjqsIi1Ac9xwnpf5tQa/icpc_dpr_2015_problem_set.pdf?dl=0)). The statement is as follows:↵
↵
Given a string S (|S| <= $10^5$) 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^6$)↵
↵
~~~~~↵
7↵
_^^_^^_↵
^__^__^↵
______↵
^^__^^↵
^_^^__^↵
^_^_^^↵
^_^_^_^^^^_^_^↵
~~~~~↵
↵
**Sample output**↵
↵
~~~~~↵
1↵
1↵
0↵
2↵
2↵
2↵
4↵
~~~~~↵
↵
