We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Suffix Rotation
  5. Discussions

Suffix Rotation

Sort by

recency

|

7 Discussions

|

  • jaredtrh20
     + 0 comments

    Here's a sol:

    int solve(const string& s) {
    vector<int> dp(s.size());
    for (char c = 'y'; c >= 'a'; --c) {
        vector<int> idx;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] >= c) {
                idx.push_back(i);
            }
        }
        if (idx.empty()) {
            continue;
        }
        vector<int> blocks;
        for (int i = 0; i + 1 < idx.size(); ++i) {
            if (s[idx[i]] == c && s[idx[i + 1]] > c) {
                blocks.push_back(i + 1);
            }
        }
        if (s[idx[0]] > c && s[idx[idx.size() - 1]] == c) {
            blocks.push_back(0);
        }
        if (blocks.empty()) {
            continue;
        }
        vector<int> pre(blocks.size());
        pre[0] = numeric_limits<int>::max() / 2;
        for (int i = 1; i < blocks.size(); ++i) {
            pre[i] = min(pre[i - 1], dp[idx[blocks[i - 1]]]);
        }
        vector<int> suf(blocks.size());
        suf[blocks.size() - 1] = numeric_limits<int>::max() / 2;
        for (int i = (int)blocks.size() - 2; i >= 0; --i) {
            suf[i] = min(suf[i + 1], dp[idx[blocks[i + 1]]]);
        }
        vector<int> dpn(s.size());
        for (int i = 0; i < blocks.size(); ++i) {
            int x = min(pre[i], suf[i]) + blocks.size() - 1;
            int j = (blocks[i] + idx.size() - 1) % idx.size();
            for (; s[idx[(j + idx.size() - 1) % idx.size()]] == c; j = (j + idx.size() - 1) % idx.size()) {
                dpn[idx[j]] = min<int>(dp[idx[blocks[i]]] + blocks.size(), x + 1);
            }
            dpn[idx[j]] = min<int>(dp[idx[blocks[i]]] + (blocks.size() == 1 ? 0 : blocks.size()), x);
        }
        int x = min(dp[idx[blocks[0]]], suf[0]) + blocks.size();
        for (int i = 0; i < idx.size(); ++i) {
            if (s[idx[i]] > c) {
                dpn[idx[i]] = x;
            }
        }
        dp = move(dpn);
    }
    return dp[0];
}

  • yashparihar729
     + 0 comments

    Here is my solution in java, Python, C, C++, Csharp HackerRank Suffix Rotation Problem Solution

  • thecodingsoluti2
     + 0 comments

    Here is Suffix Rotation problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-suffix-rotation-problem-solution.html

  • jgrandydev
     + 0 comments

    I think the problem statement needs to be cleaned-up.

    Here's my interpretation :

    A right-rotation is when all chars of the suffix block are bumped one place to the right except for the final char which jumps left to the beginning of the block.

    A left rotation is when all chars of the suffix block are bumped one place to the left except for the first char which jumps right to the end of the block ( and end of the string ).

    So in the first example problem they are performing right-rotations.

    But in Explanation 0 they instead perform left-rotations without explicitly stating such.

    Maybe this is intentional. I just think the problem is difficult enough without explicitly spelling-out what moves are being performed in the examples.

  • dmitry_r
     + 1 comment

    guys, I am stuck, I've searched the internet, read a bit about suffix arrays, Lyndon words and factorization and some other stuff, but I can not figure out how this all applicable here.

    I would greatly appreciate some hints.

    Many thanks