Reverse Shuffle Merge

Sort by

recency

|

219 Discussions

|

  • + 0 comments

    This is an optimization on several high-rated Python solutions, which used three counters, even though only two are necessary. I believe that the way I named my counters is also somewhat more intuitive given what they do, so hopefully my solution is easier to understand.

    def reverseShuffleMerge(s):
        from collections import Counter
    
        rem, out = Counter(s), ''
        reqd = {k: v // 2 for k, v in rem.items()}
    
        for curr in reversed(s):    # iterate backwards
            if reqd[curr]:              # if curr is still reqd
                while out and (prev := out[-1]) > curr and rem[prev] > reqd[prev]:
                    reqd[prev] += 1         # if prev is bigger and more remain
                    out = out[:-1]          # than reqd, put prev back in reqd
                reqd[curr] -= 1         # take curr out of reqd
                out += curr
            rem[curr] -= 1          # take curr out of remain
    
        return out
    
  • + 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;
    }
    
  • + 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)   
    
  • + 1 comment

    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.

  • + 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