CODEWITHSUNDEEP
c++string
pandaman1234
pandaman1234

Reputation: 523

Reorder a string to a string with no consecutive identical characters

The title is pretty self-explanatory, but here's a few examples:

I figured std::random_shuffle(myString.begin(), myString.end()) would be interesting since it would never do the same reordering through different calls, but it would need to be looped while the resulting string hasn't similar characters in consecutive positions. Is there a more logical way to do that reordering, or any other function doing something similar?

NOTE: The reordering doesn't need to be done randomly. A sorting function could be used, as long as identical characters are not in consecutive positions.

UPDATE: As stated in the comments...yes random_shuffle could return the same string order several times in a row. next_permutation would be more appropriate assuming the preceding approach.

Upvotes: 1

Views: 759

Answers (1)

sbeliakov
sbeliakov

Reputation: 2179

First of all note that the solution does not always exist. It exists if and only if the element with most occurrences is present no more than (n+1)/2.

So it is easy to check whether solution exists. If it exists then the following code will find it

bool cmpBySecond(const std::pair<char, int>& a, const std::pair<char, int>& b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

std::string reorder(const std::string& input) {
    std::map<char, int> cnt;
    for (auto& c: input) cnt[c]++;
    auto items = std::vector<std::pair<char, int>>(cnt.begin(), cnt.end());
    std::sort(items.begin(), items.end(), cmpBySecond);
    std::reverse(items.begin(), items.end());
    // now we have chars with occurencies counts in descending order
    std::string result(input);
    int pos = 0;
    for (auto& it: items) {
        char c = it.first;
        int times = it.second;
        for (int i = 0; i < times; ++i) {
            result[pos] = c;
            pos += 2;
            if (pos >= result.size()) pos = 1;
        }
    }
    return result;
}

The idea beyond it is to distribute the most frequent element, and then to fill gaps with the rest elements.

Also the same code with some tests here.

Upvotes: 1

Related Questions