The question statement is as follows:

Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other. All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".

The problem can be found here.

The algorithm is a greedy one, which basically works as follows:

Maintain a maximum heap of available characters, sorted by the the number of occurrences.
For each position i,
    add to the heap the chosen character at i - k
    pop out the character c with the highest number of occurrences
    set the i-th position to hold the character c
    decrease its number of occurrences by 1

This algorithm intuitively feels correct, because the characters with more occurrences are more "urgent", but I would like to prove its correctness, or at least have a proof sketch.

Currently I think this may be proved by induction on the i-th positions. Here is what I have right now:

Base case: $i=0$
In this case, all the characters are available to choose. Let's say $a$ has the maximum count but we choose $b$ instead, $count(a) > count(b)$. Then we can construct a counter example, $aab$ with $k=2$, such that if we choose b instead of a for position $0$, we fail to make the string 2 distance apart.

Induction Rule:
Suppose at position $i$, choosing the available character $a$ which has the maximum count can lead to the optimal solution. Need to prove that for $i+1$, we still need to choose the character with the maximum count.

I don't know how to finish the induction part, i.e. how to prove $i+1$ from $i$. Also, I feel the proof for the base case using counter examples is not convincing enough. Can anyone give some hints on how to prove this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.