LeetCode 358: Rearrange String k Distance Apart Solution in Python – A Step-by-Step Guide

What Is LeetCode 358: Rearrange String k Distance Apart?

LeetCode 358: Rearrange String k Distance Apart asks you to take a string and an integer k, then rearrange the string so that the same characters are at least k positions apart in the result. If it’s impossible—like having too many of one character—you return an empty string. It’s a problem of balancing frequency and spacing!

Problem Statement

• Input:
• s: String of lowercase letters.
• k: Integer representing minimum distance between identical characters.
• Output: String - Rearranged string or "" if impossible.
• Rules:
• Identical characters must be at least k positions apart (k-1 characters between them).
• Use all characters from the input string.

Constraints

• 1 <= s.length <= 3 * 10⁵
• 0 <= k <= s.length
• s consists of lowercase English letters.

Examples

• Input: s = "aabbcc", k = 3
• Output: "abcabc" (a’s are 3 apart)
• Input: s = "aaabc", k = 3
• Output: "" (3 a’s can’t be spaced 2 apart in 5 slots)
• Input: s = "a", k = 0
• Output: "a" (no spacing needed)

These show the spacing challenge—let’s solve it!

Understanding the Problem: Spacing Characters

To tackle LeetCode 358 in Python, we need to: 1. Count character frequencies. 2. Rearrange them so identical characters are k apart. 3. Check if it’s possible (e.g., max frequency fits within length constraints).

A naive approach might try all permutations, but that’s impractical. Instead, we’ll use:

• Best Solution: Max heap and queue—O(n log m) time, O(m) space—efficient and robust.
• Alternative Solution: Greedy counting—O(n log m) time, O(m) space—simpler but similar complexity.

Let’s space out with the best solution!

Best Solution: Max Heap and Queue

Why This Is the Best Solution

The max heap and queue approach runs in O(n log m) time (n is string length, m is unique characters, typically 26), using a heap to always pick the most frequent character and a queue to enforce the k-distance rule. It’s optimal for scheduling and naturally handles the constraint—making it the top choice!

How It Works

Think of it like scheduling tasks:

• Setup: Count character frequencies, use a max heap for highest counts.
• Build String:
• Pop most frequent character from heap.
• Add to result, push to queue with count-1.
• If queue reaches k, pop oldest character and re-add to heap if count remains.
• Check: If result length equals input, it’s valid.

It’s like placing characters in a line, waiting k steps before reusing!

Step-by-Step Example

For s = "aabbcc", k = 3:

• Setup:
• Counts: a:2, b:2, c:2.
• Heap: [(-2,'a'), (-2,'b'), (-2,'c')].
• Queue: [], Result: "".
• Step 1:
• Pop a (count=2), Result: "a", Queue: [(1,'a')], Heap: [(-2,'b'), (-2,'c')].
• Step 2:
• Pop b (count=2), Result: "ab", Queue: [(1,'a'), (1,'b')], Heap: [(-2,'c')].
• Step 3:
• Pop c (count=2), Result: "abc", Queue: [(1,'a'), (1,'b'), (1,'c')], Heap: [].
• Queue size = k, pop (1,'a'), push to heap: [(-1,'a')].
• Step 4:
• Pop a (count=1), Result: "abca", Queue: [(1,'b'), (1,'c'), (0,'a')], Heap: [].
• Pop (1,'b'), push to heap: [(-1,'b')].
• Step 5:
• Pop b (count=1), Result: "abcab", Queue: [(1,'c'), (0,'a'), (0,'b')], Heap: [].
• Pop (1,'c'), push to heap: [(-1,'c')].
• Step 6:
• Pop c (count=1), Result: "abcabc", Queue: [(0,'a'), (0,'b'), (0,'c')], Heap: [].
• Result: "abcabc".

For s = "aaabc", k = 3:

• Counts: a:3, b:1, c:1.
• Heap: [(-3,'a'), (-1,'b'), (-1,'c')].
• Steps: After "abc", queue holds a:2, but next a can’t fit (length=5, needs 2 gaps), fails.
• Result: "".

Code with Explanation

Here’s the Python code using heapq and deque:

Copy codefrom collections import Counter, deque
from heapq import heappush, heappop

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        # Handle edge cases
        if k <= 1:
            return s

        # Count character frequencies
        count = Counter(s)

        # Check if rearrangement is possible: max frequency <= (n+k-1)//k
        n = len(s)
        max_count = max(count.values())
        if max_count > (n + k - 1) // k:
            return ""

        # Initialize max heap (use negative counts for max heap)
        heap = []
        for char, freq in count.items():
            heappush(heap, (-freq, char))

        # Use queue to enforce k distance
        queue = deque()
        result = []

        while heap:
            freq, char = heappop(heap)  # Most frequent character
            freq = -freq  # Convert back to positive
            result.append(char)
            queue.append((freq - 1, char))  # Add with reduced count

            # When queue reaches k, release oldest character
            if len(queue) == k:
                old_freq, old_char = queue.popleft()
                if old_freq > 0:
                    heappush(heap, (-old_freq, old_char))

        # Check if all characters are used
        return "".join(result) if len(result) == n else ""

Explanation

• Lines 6-8: If k≤1, any arrangement works (no spacing needed).
• Line 11: Use Counter to count frequencies (e.g., "aabbcc" → {'a':2, 'b':2, 'c':2}).
• Lines 13-16: Feasibility check: max frequency can’t exceed slots available with k-1 gaps (e.g., n=6, k=3, max slots = (6+2)//3 = 2).
• Lines 18-20: Build max heap with negative frequencies for max priority (e.g., [(-2,'a'), ...]).
• Lines 22-34: Build result:
• Pop highest frequency character, add to result, push to queue with count-1.
• If queue hits k, pop oldest, re-add to heap if count > 0.
• Line 36: Return result if it uses all characters, else "".

• Time Complexity: O(n log m)—n operations, heap ops are O(log m), m ≤ 26.
• Space Complexity: O(m)—heap and queue store unique characters.

This is like a character scheduler—place and wait k steps!

Alternative Solution: Greedy Counting

Why an Alternative Approach?

The greedy counting method is O(n log m) too but avoids a queue, using a sorted frequency list instead. It’s simpler to follow and still efficient—good for understanding the logic!

How It Works

• Count: Get character frequencies.
• Greedy: Repeatedly pick the most frequent character, place it, reduce count, sort again.
• Check: Ensure k spacing by cycling through positions.

Step-by-Step Example

For s = "aabbcc", k = 3:

• Counts: [('a',2), ('b',2), ('c',2)].
• Result: ["", "", "", "", "", ""].
• Step 1: Place 'a': ["a", "", "", "", "", ""], a:1.
• Step 2: Place 'b': ["a", "", "b", "", "", ""], b:1.
• Step 3: Place 'c': ["a", "", "b", "", "", "c"], c:1.
• Step 4: Place 'a': ["a", "", "b", "a", "", "c"], a:0.
• Step 5: Place 'b': ["a", "", "b", "a", "", "b"], b:0 (fails k=3).
• Adjust: Use k-sized chunks: "abc" + "abc" = "abcabc".
• Result: "abcabc".

Code with Explanation

Copy codefrom collections import Counter

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s

        count = Counter(s)
        n = len(s)
        max_count = max(count.values())
        if max_count > (n + k - 1) // k:
            return ""

        # Convert to list of (count, char) and sort by count
        freq = [(cnt, char) for char, cnt in count.items()]
        result = [''] * n

        pos = 0
        while freq:
            freq.sort(reverse=True)  # Sort by frequency
            for i in range(min(k, len(freq))):
                if pos >= n:
                    break
                cnt, char = freq[i]
                result[pos] = char
                freq[i] = (cnt - 1, char)
                pos += 1
            # Remove characters with zero count
            freq = [(cnt, char) for cnt, char in freq if cnt > 0]

        return ''.join(result)

Explanation

• Lines 5-11: Handle k≤1, check feasibility.
• Line 13: Convert counts to list (e.g., [(2,'a'), (2,'b'), (2,'c')]).
• Lines 15-25: Greedily place characters:
• Sort by frequency, take up to k highest.
• Place each at next position, reduce count.
• Filter out zeros, repeat.
• Time: O(n log m)—n placements, sorting m items.
• Space: O(m)—freq list.

It’s like filling slots greedily!

Comparing the Two Solutions

• Max Heap and Queue (Best):
• Time: O(n log m)—heap operations.
• Space: O(m)—heap and queue.
• Pros: Robust, clear k enforcement.
• Cons: More complex.
• Greedy Counting:
• Time: O(n log m)—sorting.
• Space: O(m)—freq list.
• Pros: Simpler logic.
• Cons: Less explicit k handling.

Heap wins for clarity and structure!

Additional Examples and Edge Cases

• s="a", k=0: "a".
• s="aaa", k=2: "" (impossible).
• s="abcd", k=2: "abcd".

Both handle these well.

Complexity Breakdown

• Heap and Queue: O(n log m) time, O(m) space.
• Greedy: O(n log m) time, O(m) space.

Both are efficient, heap is more elegant.

Key Takeaways

• Heap and Queue: Smart scheduling—top efficiency!
• Greedy: Simple placement—easy to grasp!
• Spacing: Frequency rules.
• Python Tip: Heapq and Counter shine—see [Python Basics](/python/basics).

Final Thoughts: Space Those Characters

LeetCode 358 in Python is a spacing challenge. Heap and queue excel, while greedy counting builds intuition. Try LeetCode 767 next. Visit Solve LeetCode 358 and rearrange today!