Reorganize String With PQ | Dataford Interview Questions

Your question is Reorganize String With PQ. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

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):