You are viewing a single comment's thread. Return to all 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]; }
Seems like cookies are disabled on this browser, please enable them to open this website
Suffix Rotation
You are viewing a single comment's thread. Return to all comments →
Here's a sol: