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.
Built frequency hash-map for char and occurences. Original word has half of the occurence of every char
Reverse the original string and try to construct the smallest lexicographic one
While iterating, use a stack (the idea somehow resembles the largest rectangle problem, from stack category).
If the new char occurs already n/2 times, where n = frequency of the original / 2, then skip this char, since we can not, nor we should push it to the stack
else pop chars from the stack, if: stack is not empty, top char stack is greater than the new char and by removing the top char we still can build the word with desired frequency
Python solution, inspired by @mbrotma1's solution.
deffrequency(s):res=defaultdict(int)forcharins:res[char]+=1returnres# Complete the reverseShuffleMerge function below.defreverse_shuffle_merge(s):char_freq=frequency(s)used_chars=defaultdict(int)remain_chars=dict(char_freq)res=[]defcan_use(char):return(char_freq[char]// 2 - used_chars[char]) > 0defcan_pop(char):needed_chars=char_freq[char]// 2returnused_chars[char]+remain_chars[char]-1>=needed_charsforcharinreversed(s):ifcan_use(char):whileresandres[-1]>charandcan_pop(res[-1]):removed_char=res.pop()used_chars[removed_char]-=1used_chars[char]+=1res.append(char)remain_chars[char]-=1return"".join(res)
Reverse Shuffle Merge
You are viewing a single comment's thread. Return to all comments →
Python solution, inspired by @mbrotma1's solution.