 # LAST05-Editorial

Author: [Vivek Kumar Mishra(vkm41101 | CodeChef User Profile for Vivek Kumar Mishra | CodeChef)
Tester: Vivek Kumar Mishra
Editorialist: Harshit Pandey

MEDIUM

Prefix Array

# 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”;

}

}