PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Kanhaiya Mohan
Tester: Nishant Shah, Divyansh Tyagi, Syed Ali Aatif
Editorialist: Akshit Dhoundiyal
DIFFICULTY
Easy
PREREQUISITES
Basic observation, Substring Manipulation
PROBLEM
Given a string S consisting of N upper-case letters. You need to determine the maximum length of the string that can be obtained in at most K operations such that the number of distinct letters in it is 1. In one operation you can select a prefix, of any size, from the string and remove a suffix of that prefix, of any size, from the string.
EXPLANATION
To understand how a given string is finally converted to a string with all the letters the same (or to an empty string) by performing at most K moves, we first need to figure out how a move changes the current string.
Exploring “a move”
A single valid move consists of:
- Taking out a substring of any size from the left side of the string.
- Removing a part of any size from the right of that removed substring.
- Adding back the remaining substring to the front of the initial remaining string.
In other words, each move is equivalent to removing any subarray from the string.
→ Example:
Consider the string ABCDEFG, before and after a valid move.
By observation, we can see that at the end of a valid move, a substring of the given string is removed.
***Note: ***We find the maximum length of string that can be obtained for each letter of the English alphabet one by one. The maximum out of those values will be our answer for the test case.
Procedure to find the maximum length of string for a letter under consideration:
Considering the sample test case 1 with the letter A:
We start with the division of the complete string into 3 parts - prefix, middle and suffix.
Prefix and suffix are groups of maximum contiguous occurrences of the letter from the beginning and the end of the string respectively. The remaining part of the string is the middle part.
We then traverse through the middle part to find similar groups of contiguous occurrences of the letter. The sizes of all such groups encountered is pushed into an array, which is reverse-sorted afterwards.
With maximum K moves (K>0), we can select K-1 groups in the order of decreasing size from the middle part. In other words, we take out the first K-1 elements exhaustively from the array.
The sum of the sizes of such groups is the maximum length that can be obtained for that letter.
For letter A, in this case, the max length will be 1+(1)+1 = 3
Finally, the maximum value of all the max lengths for each letter is our answer
Check out these additional examples for a clearer understanding of internal cases with letters.
→ Alternate example 1:
For N = 13, K = 4 moves
Maximum length for letter A = 2 + (3+2+1) + 0 = 8
The substrings hypothetically deleted in the 4 moves are {B, C, BD, E} in no particular order.
→ Alternate example 2:
For N = 13, K = 3 moves
Maximum length for letter A = 2 + (3+2) + 0 = 7
The substrings hypothetically deleted in the 3 moves are {B, CABD, E} in no particular order.
→ Alternate example 3:
For N = 13, K = 3 moves
Maximum length for letter B = 0 + (1+1) + 0 = 2
The substrings hypothetically deleted in the 3 moves are {AA, AACA, DAAAE} in no particular order.
Special Case 1: If K = 0,
In this case, our initial string and the final string will be the same for all the letters, as we cannot make any changes to the string. If the string contains any letter other than the letter under consideration, then the max length for that string will be 0. On the other hand, if the string only consists of that letter, then the max length will be the length of the string itself.
Special Case 2: If K != 0 and the string just contains 1 unique letter,
Using the approach discussed above will lead to an error in this case. Here’s why:
The prefix and suffix parts will cover the entire string when the letter under consideration and the unique letter in the string are the same, so the final answer produced will be twice the length of the string.
But the answer for this case should be N, where N is the length of the string. So, if we return min(N, prefix+middle+suffix), then this condition will be automatically taken care of.
