6
\$\begingroup\$

Problem: Given a string str and array of pairs that indicates which indices in the string can be swapped, return the lexicographically largest string that results from doing the allowed swaps. You can swap indices any number of times.

Example

For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be swapLexOrder(str, pairs) = "dbca".

By swapping the given indices, you get the strings: "cbda", "cbad", "dbac", "dbca". The lexicographically largest string in this list is "dbca".

My comments: My program passed all the tests on the CodeSignal website, but since I am relatively new to algorithms, there's probably a more efficient way to solve it. In addition, I'm looking for general code review: does my code have signs that I look like a beginner? thank you.

#include<iostream>
#include<set>
#include<string>
#include<vector>
#include<map>
#include<algorithm>

std::string swapLexOrder(std::string str, std::vector<std::vector<int>> pairs)
{
    if(pairs.size() == 0) return str;
    std::vector<std::set<int>> pairpool; //pairpool : contains sets of interchangeable indices
    std::vector<std::vector<std::string>> stringpool; //stringpool : contains vectors of interchangeable characters

    //creates pairpool structure
    for(std::size_t i = 0; i < pairs.size(); i++)
    {
        bool alrExists = false;
        std::set<int> newSet;
        for(auto& p : pairpool)
        {
            for(auto ele : p)
            {
                if((pairs[i][0] == ele) || (pairs[i][1] == ele))
                {
                    if(!alrExists)
                    {
                        alrExists = true;
                        p.insert(pairs[i][0]);
                        p.insert(pairs[i][1]);
                        newSet = p;
                    }
                    else
                    {
                        if(p == newSet) break;
                        p.insert(newSet.begin(), newSet.end());
                        pairpool.erase(std::remove(pairpool.begin(), pairpool.end(), newSet), pairpool.end());
                        break;  //  needed this break statement really badly
                    }
                }
            }
        }
        if(!alrExists)
        {
            newSet.insert(pairs[i][0]);
            newSet.insert(pairs[i][1]);
            pairpool.push_back(newSet);
        }
    }

    //creates sorted stringpool structure
    for(auto p : pairpool)
    {
        std::vector<std::string> newset;
        for(auto ele : p)
        {
            newset.push_back(str.substr(ele - 1, 1));
        }
        std::sort(newset.begin(), newset.end());
        stringpool.push_back(newset);
    }

    //uses stringpool and pairpool to modify string only one time through
    int counter = 0;
    for(auto p : pairpool)
    {
        for(auto ele : p)
        {
            str.replace(ele - 1, 1, stringpool[counter].back());
            stringpool[counter].pop_back();
        }
        counter++;
    }

    return str;
}

int main()
{
    std::cout << swapLexOrder("acxrabdz", {{1, 3}, {6, 8}, {3, 8}, {2, 7}}) << "\n";
    std::string STR = "lvvyfrbhgiyexoirhunnuejzhesylojwbyatfkrv";
    std::vector<std::vector<int>> PAIR =
    {
        {13, 23},
        {13, 28},
        {15, 20},
        {24, 29},
        {6, 7},
        {3, 4},
        {21, 30},
        {2, 13},
        {12, 15},
        {19, 23},
        {10, 19},
        {13, 14},
        {6, 16},
        {17, 25},
        {6, 21},
        {17, 26},
        {5, 6},
        {12, 24}
    };
    std::cout << swapLexOrder(STR, PAIR) << "\n";
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I guess one minor thing I see in my code is I have a #include<map> when I didn't use a hashmap. \$\endgroup\$ – Bo Work Dec 26 '18 at 0:20
4
\$\begingroup\$

Your code is quite good for a beginning, but there's still much room for improvement. Your code main flaw is that it is difficult to read. There are also some performance issues, but they are a lot easier to correct.

N.B: I'll stay close to your algorithm, although you could probably find a better one in a graph library (see for instance https://en.wikipedia.org/wiki/Connected_component_(graph_theory)#algorithms)

Performance

You must pick your types more carefully. Don't choose a type that allocates memory when you can use one that doesn't. For instance, don't represent a pair of indices by a std::vector: a pair will always have two elements, there is no need to ever grow it. So choose a std::pair<int, int> instead: it is lighter, quicker, and reflects your intent more clearly. In the same way, don't use std::string to represent 1 character: your stringpool can as well be of type std::vector<std::string>.

You must also be more careful while passing objects around. Don't pass large objects by value unless you need both to copy and modify them. For instance, the signature: std::string swapLexOrder(std::string str, std::vector<std::vector<int>> pairs) is only partially correct. You will indeed modify str, and you want the user to keep his original string untouched, so passing by value is a good call. But pairs is read-only in your code, so pass it by const reference.

Expressiveness

Your code is one big function containing a lot of nested loops. As a result,it's very hard to understand, let alone optimize. There is two ways to fix it: the first is to better comment on your algorithm (for instance, a minimum would be: first, we merge all pairs of indices that are connected together; then we extract the corresponding characters from the input string, sort them in decreasing order and put them back); the second, is to make your code express your intent clearly.

The most important rule, which also is one of the hardest to obey, is to choose meaningful names. newset doesn't mean much, neither does p. pairpool should not contain set of more than two elements.

Another way to write more expressive code is to avoid "raw loops". Use named algorithms instead. For instance, I rewrote the first part of your algorithm as a combination of a partition discriminating sets containing one element of the considered pair and an accumulation which merges them:

std::string swapLexOrder(std::string str, const std::vector<std::pair<int, int>>& pairs)
{
    if(pairs.size() == 0) return str;
    std::vector<std::set<int>> index_permutations; //pairpool : contains sets of interchangeable indices

    for(auto pair : pairs)
    {   
        // [matches, end) <- sets containing either one of the pair's elements   
        auto matches = std::partition(index_permutations.begin(), index_permutations.end(), 
                                      [&pair](const auto& permutation_set) {
            return std::none_of(permutation_set.begin(), permutation_set.end(), [&pair](auto index) {
                return index == pair.first || index == pair.second;
            });
        });

        if (matches == index_permutations.end()) index_permutations.push_back({pair.first, pair.second});
        else { // merge matches
            *matches = std::accumulate(matches, index_permutations.end(),
                                       std::set<int>{pair.first, pair.second},
                                       [](auto&& init, auto&& permutation) {
                init.insert(permutation.begin(), permutation.end());
                return init;
            });
            index_permutations.erase(std::next(matches), index_permutations.end());
        }
    }
// ...

Here's a link to the partially rewritten code if you want to experiment with it: https://wandbox.org/permlink/6Wij6Y4NuooMlW6C

\$\endgroup\$
2
\$\begingroup\$

You are allocating and deallocating memory all over the place. That is not only an expensive operation by itself, it also destroys locality of reference, and wastes much memory for bookkeeping:

  • A std::vector<T> is quite an extravagance where a simple std::pair<T, T> suffices.
  • A std::set is a sorted, node-based container. Convenient, but better use a std::vector and sort it once.
  • The only good thing about the std::string in the stringpool is that a single character will not allocate an extra-buffer due to SSO.
  • The least you can do with newSet is std::move() it.
  • Same for newset. Did you see the different casing there?
  • How you copy complex elements in the for-range-loops is just cruel.
  • You could std::move() the return-value. Not that it makes that much difference after the rest.

Iterating over candidate-sets is a very slow way to find clusters of interchangable elements. Just use a proper union-find-datastructure.

Thus, while your code may work, it is really slow, especially as the problem-size grows O(n²) will become problematic.

An alternative, doing only three allocations, and using a proper union-find-datastructure, reducing time-complexity to O(n*log(n)):

auto findUnion(
    std::size_t n,
    std::span<std::pair<std::size_t, std::size_t>> pairs
) {
    std::vector<std::size_t> r(n);
    std::iota(begin(r), end(r), n-n);
    const auto find = [&](auto a){
        if (a == r[a])
            return a;
        return r[a] = find(r[a]);
    };
    for (auto [a, b] : pairs) {
        if (a < 0 || b < 0 || a >= n || b >= n)
            throw std::out_of_range();
        a = find(a);
        b = find(b);
        r[a] = r[b] = std::min(a, b);
    }
    for (auto& x : r)
        x = r[x];
    return r;
}

auto findLargest(
    std::string s,
    std::span<std::pair<std::size_t, std::size_t>> pairs
) {
    const auto n = size(s);
    const auto unions = findUnion(n, pairs);
    std::vector<std::size_t> indices(n);
    std::iota(begin(indices), end(indices), n-n);
    std::sort(begin(indices), end(indices), [&](auto a, auto b){
        return std::tie(unions[a], a) < std::tie(unions[b], b);
    });
    std::vector<char> buffer(n);
    for (auto i = n-n; i < n;) {
        auto j = i;
        for (; j < n && unions[indices[j]] == unions[indices[i]]; ++j)
            elements[j - i] = s[indices[j]];
        j -= i;
        if (j > 1) { // need not be optional
            std::sort(data(buffer), data(buffer) + j);
            while (j)
                s[indices[i++]] = buffer[--j];
        }
    }
    return std::move(s);
}
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.