You are viewing a single comment's thread. Return to all comments →
For guys looking for simpler solution with low complexity, here's my submission (40 lines of code in C and 0s execution time for all test cases).
If the input string is S and the required answer is A, then the basic idea is as follows :
1) Store the count of each character (a to z) in S.
2) Update the count of characters required for A by dividing by 2.
3) Select each character for A by parsing S from right to left.
4) One "can" afford to "not select" a character, if its required-count for A will be fulfilled even after leaving it.
5) Considering point 4, always select smallest character if possible.
6) If a character can't be left (point 4 invalid), select the smallest character seen so far (even if it is not smallest for the entire string).
7) Ignore characters not required for A anymore.
Informative Tweets for Inquisitive Minds
Seems like cookies are disabled on this browser, please enable them to open this website
Reverse Shuffle Merge
You are viewing a single comment's thread. Return to all comments →
For guys looking for simpler solution with low complexity, here's my submission (40 lines of code in C and 0s execution time for all test cases).
If the input string is S and the required answer is A, then the basic idea is as follows :
1) Store the count of each character (a to z) in S.
2) Update the count of characters required for A by dividing by 2.
3) Select each character for A by parsing S from right to left.
4) One "can" afford to "not select" a character, if its required-count for A will be fulfilled even after leaving it.
5) Considering point 4, always select smallest character if possible.
6) If a character can't be left (point 4 invalid), select the smallest character seen so far (even if it is not smallest for the entire string).
7) Ignore characters not required for A anymore.
Informative Tweets for Inquisitive Minds