Find all cyclic permutations of a string in O(n)

Question

Given the problem: Find all cyclic permutations of a string

For example: given a string: "abcd"

All the cyclic permutations of a string would be: "abcd", "dabc", "cdab", "bcda"

Here's what I have tried out:

for(int i = 0; i < str.size(); i++){
    permu.push_back(str);
    str.insert(0, 1, str[str.size()-1]);
    str.erase(str.end()-1);
}

I got Time-limit-exceeded since the insert and erase function takes O(n) making the overall solution O(n^2)

Is there anyway to solve this in O(n) or less?

Answer 1

Here's another approach if you don't want to create another string:

for(int i = 0; i < str.size(); i++)
    permu.push_back(str.substr(i) + str.substr(0, i));

Answer 2

You can use string_view to do it in O(n):

std::vector<std::string_view> get_perms(std::string& str) {
    auto orig_length = str.length();
    str += str;
    std::vector<std::string_view> ret;

    std::string_view sv{str};
    for (int i = 0; i < orig_length; i++) {
        auto sv2 = sv.substr(i, orig_length);
        ret.push_back(sv2);
    }
    return ret;
}

Taking a substring of a string_view is constant time, but you need to ensure the original string stays alive. This is why the function takes str as a non-const reference.