PROBLEM LINK:
Author: [Vivek Kumar Mishra(vkm41101 | CodeChef User Profile for Vivek Kumar Mishra | CodeChef)
Tester: Vivek Kumar Mishra
Editorialist: Harshit Pandey
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
Find the cost of making a string beautiful by removing palindromic substrings
QUICK EXPLANATION:
Use a Prefix Array
EXPLANATION:
Note that in the beautiful string si≠si−1 (because it is a palindrome of length 2) and si≠si−2 (because it is a palindrome of length 3). This means si=si−3, i.e. a beautiful string has the form abcabcabc…, up to the permutation of the letters a, b and c.
For each permutation of the letters a, b and c, we will construct a string t, of the form abcabcabc… of length n. Let’s define an array a of length n as follows: ai=0 if si =ti (i.e. the character at the i-th position does not need to be changed) and ai=1 otherwise. Let’s build an array pr of prefix sums of the array a. Now you can process a query of the number of positions that need to be replaced for the current line t in O(1).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<vector> pr(6, vector(n + 1));
string t = “abc”;
int cur = 0;
do {
for (int i = 0; i < n; ++i)
pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]);
++cur;
} while (next_permutation(t.begin(), t.end()));
while (m–) {
int l, r;
cin >> l >> r;
int ans = n;
for (int i = 0; i < 6; ++i)
ans = min(ans, pr[i][r] - pr[i][l - 1]);
cout << ans << “\n”;
}
}