[Algorithm] Rearrange String k Distance Apart

Rearrange String k Distance Apart

Problem Statement:

Given a non-empty string str 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"".

Solution : Sorting + Greedy

This one is actually very good problem, sharing my thinking process a bit.

(Idea A) Initially I was thinking naively as counting all the occurrences of each char and inserting by its alphabetical order, keep track of the previous added character count and compare it with k, if the previous added count is smaller than k, meaning the distance between the first character must be smaller than k. This logic is flawed because I didn't consider this:

"abbcc", k = 2

The condition of previous added count greater than k will not guarantee us that same character will be k distance apart, simply because the head of alphabetical sequence is no longer available.

(Idea B) Then I began to think that we probably should use the frequency of each character as the order instead of alphabetical order. For example:

"abbcc" is:

a : 1

b : 2

c : 2

Rendering an order of "b->c->a" for insertion, because we are inserting every possible characters during each iteration so that this order will be kept throughout the process. But this one is still flawed in this case:

"aaabc", k = 2

The second and third "a" will automatically be false no matter what. The above approaches are bad because I was trying to maximize the distance possible between two characters, since the total length of string is fixed, meaning this direction of greedy will make some substring fall short of the constraint.

So this suggests that the greedy should be taken in another direction, which is minimum distance possible which satisfy the constraint. Actually when we think about this way, we shed some light upon one important condition:

To make sure that same char is k distance apart, we just need to ensure that in each window of size k, there's no duplicate letter. And to make sure across each window we can use the order that (Idea B) was using. But instead of fixing the order upfront, we need to update this order after each window of insertion. This will guarantee that each letter inside the window will be kept at the largest distance to the next window. (If the distance is smaller than k, this suggests rearrangement is impossible).

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: typedef pair<int, char> Node; string rearrangeString(string str, int k) { if (k == 0) return str; vector<Node> letters(26); for (char c : str) { letters[c - 'a'].first++; letters[c - 'a'].second = c; } reorderLetters(letters); string result; int depletion = 0; while (!letters.empty()) { if (k > letters.size() && (++depletion) > 1) return ""; for (int i=0; i<k && i<letters.size(); i++) { result += letters[i].second; letters[i].first--; } reorderLetters(letters); } return result; } inline void reorderLetters(vector<Node>& letters) { if (letters.empty()) return; std::sort(letters.begin(), letters.end(), [](const Node& lhs, const Node& rhs) { if (lhs.first == rhs.first) return lhs.second < rhs.second; return lhs.first > rhs.first; }); while (!letters.empty() && letters.back().first == 0) { letters.pop_back(); } } };