Reorganize String With PQ

HardPython

Problem

Micro1's assessment platform needs to reorder characters in a generated access token so repeated characters are separated. Given a lowercase string s and an integer k, return any rearrangement in which identical characters are at least k positions apart. Return an empty string if no valid rearrangement exists.

Formal Specification

Implement reorganize_string(s, k).

Input: s, a string of lowercase English letters, and k, a positive integer.
Output: A string containing exactly the same characters as s, with every pair of equal characters separated by at least k positions, or "" if impossible.
If k == 1, every permutation is valid, so returning s is acceptable.

Use a max-priority queue for characters currently available and a min-priority queue for characters still in cooldown. At each position, release eligible characters, choose the available character with the greatest remaining frequency, and place it in the result.

Constraints

1 <= len(s) <= 10^5
s contains only lowercase English letters
1 <= k <= len(s)
Any valid rearrangement is accepted

Function Signature

def reorganize_string(s, k):

Formal Specification

Implement reorganize_string(s, k).

Input: s, a string of lowercase English letters, and k, a positive integer.
Output: A string containing exactly the same characters as s, with every pair of equal characters separated by at least k positions, or "" if impossible.
If k == 1, every permutation is valid, so returning s is acceptable.