Discussion on Reverse Shuffle Merge Challenge

5 days ago+ 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

Cookie support is required to access HackerRank