358.Rearrange String k Distance Apart

Tags: [queue], [heap], [max_heap], [map], [trick]

Com: {g}

Hard: [###]

Link: https://leetcode.com/problems/rearrange-string-k-distance-apart/#/description

Given a non-empty stringsand an integerk, rearrange the string such that the same characters are at least distancekfrom each other.

All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string"".

Example 1:

s = "aabbcc", k = 3
Result: "abcabc"
The same letters are at least distance 3 from each other.

Example 2:

s = "aaabc", k = 3 
Answer: ""
It is not possible to rearrange the string.

Example 3:

s = "aaadbbcc", k = 2
Answer: "abacabcd"
Another possible answer is: "abcabcda"
The same letters are at least distance 2 from each other.

Solution: Map:

class Solution(object):
    def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        if not s:
            return ''

        counts = collections.defaultdict(int)
        valid_map = collections.defaultdict(int)
        for c in s:
            counts[c] += 1
            valid_map[c] = -1

        rest = []
        while True:
            c = self.select_c(counts, valid_map, len(rest))
            if not c:
                return ''

            rest.append(c)
            counts[c] -= 1
            valid_map[c] = len(rest) - 1 + k

            if len(rest) == len(s):
                break

        return ''.join(rest)

    def select_c(self, counts, valid_map, index):
        max_count = -1
        selected_c = None

        # because there are just 26 chars,
        # so the 'select_c' function take T = O(1).
        for c in counts:
            if counts[c] > 0 and index >= valid_map[c]:
                if counts[c] > max_count:
                    max_count = counts[c]
                    selected_c = c

        return selected_c

Note:

• Time complexity = O(n), n is the length of the given string.

Solution: Queue, Heap

import heapq

class Solution(object):
    def rearrangeString(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        if not s:
            return ''

        chars = collections.defaultdict(int)
        for c in s:
            chars[c] += 1

        max_heap = []
        for c in chars:
            max_heap.append((-chars[c], c))

        rest = []
        heapq.heapify(max_heap)
        waiting_queue = collections.deque()
        while max_heap:
            count, c = heapq.heappop(max_heap)
            count = -count

            rest.append(c)
            count -= 1

            waiting_queue.append((count, c))
            if len(waiting_queue) >= k:
                count, c = waiting_queue.popleft()
                if count:
                    heapq.heappush(max_heap, (-count, c))

        return ''.join(rest) if len(rest) == len(s) else ''

Revelation:

• This problem can be solved by greedy strategy. Each time choose the char who has the biggest remaining counts, so we can use max heap to finish this task.
• Using queue to queue the chars which have just been used, and once the queue size >= k, we popleft one char, if at this moment this char's count > 0, then we push it back into max heap.
• The reason we are checking the len(queue) >= k (not just len(queue) == k), because there exists the case: s = 'aa', k = 0.
• Finally we need check len(rest) == len(s).

Note:

• Time complexity = O(n + nlgn) = O(nlgn), n is the length of the given string.