Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.
Input: { a, b, b }, distance = 2
Output: { b, a, b }
I think it’s quite an interesting question. So if you want to do some brainstorming and do not wish to spoil the fun, please feel free to do so and beware of the spoilers ahead.
*** Spoilers alert! ***
*** Spoilers alert! ***
The solution below involves a greedy strategy, that is: The character that has the most duplicates has the highest priority of being chosen to put in the new list. If that character cannot be chosen (due to the distance constraint), we go for the character that has the next highest priority. We also use some tables to improve the efficiency. (i.e., keeping track of # of duplicates of each character.)
Read full article from String Reorder Distance Apart | LeetCode
No comments:
Post a Comment