We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Reverse Shuffle Merge
  5. Discussions

Reverse Shuffle Merge

  • gschoen
     + 0 comments

    Problems like these are solved using a "Monotonic Stack". The idea is to iterate through the string backwards and for keep popping off characters from the stack (as long as there are enough remaining characters of that type in the string) that have a value that is greater than that of the current character then pushing the current character onto the stack.

    #include <stdio.h>

char *reverseShuffleMerge(char *s, char *result, int n) {
    int j = 0;
    result[n] = '\0';
    int available[26] = {}, required[26];
    for (int i = 0; s[i]; ++i) ++available[s[i] - 'a'];
    for (int i = 0; i < 26; ++i) required[i] = available[i] >> 1;
    for (int i = (n << 1) - 1; i >= 0; --i) {
        char c = s[i];
        int t = c - 'a';
        if (!required[t]) {
            --available[t];
            continue;
        }
        while (j > 0 && c < result[j-1] && 
          available[result[j-1] - 'a'] > required[result[j-1] - 'a']) {
            ++required[result[--j] - 'a'];
        }
        result[j++] = c;
        --required[t];
        --available[t];
        if (j == n) break;
    }
    return result;
}
int main() {
    char s[10001];
    scanf("%s", s);
    int n = strlen(s) >> 1;
    char result[n+1];
    printf("%s\n", reverseShuffleMerge(s, result, n));
    return 0;
}