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

Sort by

recency

|

218 Discussions

|

  • 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;
}

  • chenji2012
     + 1 comment
    def reverseShuffleMerge(s):
    # Write your code here
    
    stashed_dic = Counter(s)
    # the intial requirments for each char
    required_dic = {c:math.ceil(v/2) for c,v in stashed_dic.items()}
    
    result = []
    
    for c in reversed(s):
        stashed_dic[c] -= 1
        if required_dic[c] <= 0:
            continue
        # deal with the pop    
        while result:
            last_c = result[-1]
            if (c < last_c ) and (stashed_dic[last_c] >= required_dic[last_c] + 1):
                result.pop()
                required_dic[last_c] += 1 
            else:
                break
        result.append(c)
        required_dic[c] -= 1
        
    return  "".join(result)

  • kunal_zodape
     + 0 comments

    I still don't understand how when, string = "abcdefgabcdefg" then "agfedcb" is the lexicographically smallest. All my approaches give me"abcdefg". Like it is actually genuinely frustrating how it is messing with my mind. I truly hate this question for wasting my time as I don't even feel like I am learning anything here, just trying to understand the question itself is driving me insane.

  • daideneg4
     + 0 comments

    If a secure and reliable gaming experience is what you’re after, BanzaiBet is the perfect choice. Their platform ensures safety with trusted payment methods like mobile and cryptocurrency options, which you can learn more about by visiting https://banzaibet-bd.com/ ,great platform. What’s more, their collection of slots is impressive, featuring themes inspired by everything from timeless classics to popular movies and video games. It’s a great spot for anyone

  • 1337er
     + 1 comment

    O(n) time complexity because even with nested while loop an element of s is only pushed and popped a maximum of 1 times

    from collections import Counter

def reverseShuffleMerge(s):
    char_counts = Counter(s)
    required = Counter()
    for key, value in char_counts.items():
        required[key] = value // 2
    last_char = s[-1]
    char_counts[last_char] -= 1
    required[last_char] -= 1
    result = [last_char]
    for i in range(len(s)-2, -1, -1):
        char = s[i]
        char_counts[char] -= 1
        if not required[char]:
            pass
        elif (not result) or (char >= result[-1]):
            result.append(char)
            required[char] -= 1
        else:
            while result and char < result[-1] and char_counts[result[-1]] >= required[result[-1]] +1:
                old_char = result.pop(-1)
                required[old_char] += 1
            result.append(char)
            required[char] -= 1
    return "".join(result)