Python solution with detailed explanation


  • 0
    G

    Solution

    Rearrange String k Distance Apart https://leetcode.com/problems/rearrange-string-k-distance-apart/

    Algorithm

    • Note there are two versions. One version of the problem is "Rearrange String Exactly k Distance Apart". Solution 1 has the solution for it. It is also mentioned in geekforgeeks.
    • Our problem is: "Rearrange String atleast k Distance Apart"
    • For every position in the result, fill it with the character with the highest frequency as long as it can be filled validly. Validity means to ensure that the previous occurence of this charcter was k apart.
    from collections import Counter        
    class Solution(object):
        def rearrangeString(self, s, k):
            """
            :type str: str
            :type k: int
            :rtype: str
            """
            f_map = Counter(s)
            result = [None]*len(s)
            last = {}
            for i in range(len(s)):
                max_ch, max_f = None, 0
                # Iterate all elements in frequency map and pick the valid one with highest frequency.
                for k1,v1 in f_map.items():
                    if (v1 > max_f) and (k1 not in last or last[k1]+k<=i):
                        max_ch, max_f = k1,v1
                if max_ch == None:
                    return ""
                # Add the character to result. Reduce the frequency. Update the position for last occurence.
                result[i] = max_ch
                f_map[max_ch] = f_map[max_ch] - 1
                last[max_ch] = i
            return "".join(result)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.