Last Updated: 26 Nov, 2021
Pretty Strings Workshop
Hard
Asked in companies
Ninja runs a workshop where he converts a string to a pretty string. A pretty string is a string that does not contain a substring of length at least 2, which is a palindrome. The cost of a string is the minimum number of operations required to convert the string into a pretty string. In one operation, the ninja can change any character of the string to one of the first three letters of the English alphabet. As ninja is good at string processing but incompetent at math. So, can you help ninja in calculating the cost of the strings?
You are given a string ‘STR’ containing only the first three letters of the English alphabet and ‘M’ queries. In each query, you have to find the cost of the substring of the ‘STR’ from index ‘L’ to ‘R’.
For example:
You are given ‘STR’ = “aabac” and ‘QUERIES’ = [[1, 3], [2, 5]].
Then the answer of the first query will be 1 as we can convert the substring “aab” to “acb” by converting ‘a’ at index 2 to ‘c’ to get a pretty string.
The answer for the second query will be 1 as we can convert the substring “abac” to “cbac” by converting ‘a’ at index 2 to ‘c’.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line contains two space-separated integers, ‘N’ and ‘M’, denoting the length of the input string and the number of queries, respectively.
The second line of each test case contains a string denoting the input string.
The following ‘M’ lines contain two space-separated integers, ‘L’ and ‘R’, denoting the start and end index(1-indexed) of the substring of the string, respectively.
Output Format:
For each query, print the cost of the substring to the string from index ‘L’ to ‘R’.
The output for each test case will be printed in a separate line.
Constraints:
1 <= T <= 10
1 <= N <= 2000
‘STR’ contains only ‘a’, ‘b’ or ‘c’.
1 <= M <= 2000
1 <= L <= N
L <= R <= N
Time limit: 1 sec
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Approaches
There can be only six possible ways to create a pretty string:
- Repeatedly appending “abc”(abcabcabc…).
- Repeatedly appending “acb”(acbacbacb…).
- Repeatedly appending “bca”(bcabcabca…).
- Repeatedly appending “bac”(bacbacbac....).
- Repeatedly appending “cba”(cbacbacba…).
- Repeatedly appending “cab”(cabcabcab…).
So, we compare the input string with all the possible pretty strings and convert it into the pretty string, requiring a minimum number of operations. We will store the mismatched character count in a ‘DP’ table and answer the queries in O(1) using the ‘DP’ table. For example,
Now, if we have to find the cost substring of the input string from index ‘L’ to ‘R’, then the cost will be MINIMUM(‘DP[‘I’][‘R’] - ‘DP’[‘I’][‘L] - 1]) where ‘I’ is the ‘I’th pretty string.
Algorithm:
- Initialize a 2-D array ‘POSSIBLECOMB’ to store all possible combinations of a pretty string.
- Initialize a 2-D array ‘DP’ to store the count of mismatched characters for every possible combination.
- Iterate ‘I’ in 0 to 6:
- Set ‘COUNT’ as 0.
- Iterate ‘J’ in 1 to ‘N’:
- If there is a mismatch between the current pretty string’s character and the input string’s character:
- Increment ‘COUNT’ by 1.
- Set ‘DP’[‘I’][‘J’] as ‘COUNT’.
- If there is a mismatch between the current pretty string’s character and the input string’s character:
- Initialize an array ‘ANS’ to store the answer to each query.
- Iterate ‘I’ in 0 to ‘M’:
- Set ‘L’ as ‘QUERIES’[‘I’][0].
- Set ‘R’ as ‘QUERIES’[‘I’][1].
- Initialize a variable ‘MIN’.
- Iterate ‘J’ in 0 to 6:
- Set ‘MIN’ as the minimum of (‘DP[‘J’][‘R’] - ‘DP’[‘J’][‘L] - 1]).
- Set ‘ANS’[‘I’] as ‘MIN’.
- Return ‘ANS’.
Similar problems