PROBLEM LINKS
DIFFICULTY
SIMPLE
PREREQUISITES
Greedy
PROBLEM
We are given a string S. Each character of S is either a question mark (’?’) or an uppercase letter (‘A’-‘Z’). Replace each question mark with an uppercase letter in such a way that the resulting string contains as many “CHEF” as possible. If there is more than one possible resulting string, output the lexicographically smallest one.
QUICK EXPLANATION
Iterate the string S from the end of the string to the beginning. Each time we can replace the current positions with the string “CHEF”, we replace with it. Then, change all remaining question marks with character 'A’s.
EXPLANATION
First, let’s introduce some notations.
- N = the number of characters of S.
- S[i] = the i-th character of S (1-based).
- S[i..j] = the substring of S consisting of the i-th character of S through the j-th character of S.
Then, let’s introduce an intuitive yet important lemma.
Lemma 1. All occurrences of "CHEF"s in S must be non-overlapping.
Proof. The string “CHEF” cannot overlap with itself because it consists of 4 distinct characters. This is in contrast to, for example, string “ABAB”, which can overlap with itself. In this case, we can have a string with two overlapping "ABAB"s: “ABABAB”.
Now that Lemma 1 is proved, we can come up with the following theorem.
Theorem 1. Consider any string S. If we can replace S[1…4] with “CHEF”, then it is optimal to replace it.
Proof. The proof is by contradiction. Suppose that S can contain at most X "CHEF"s. Since "CHEF"s cannot overlap each other, the next occurrences of "CHEF"s must be at least from position 5. If we do not replace S[1…4], all occurrences of "CHEF"s must be contained in S[5…N]. Let Y be the maximum number of "CHEF"s that S[5…N] can contain. For Theorem 1 to be not optimal, it must be the case that Y > X. But it is not impossible, because:
X = the maximum number of "CHEF"s in S[1…N]
= the maximum number of "CHEF"s in S[1…4] concatenated with S[5…N]
= 1 + Y.
By Theorem 1, we can derive the following greedy solution.
for i = 1; i ≤ N-3; i++:
if can_replace(S[i..i+3], "CHEF"):
replace(S[i..i+3], "CHEF")
Now, let’s move to the next lemma.
Lemma 2. All remaining occurrences of '?'s in S that were not replaced by the previous iteration should be replaced with ‘A’.
Proof. We want to have the lexicographically smallest resulting string. The lexicographically smallest letter is ‘A’, so it is always better to replace the question marks with 'A’s.
It seems that now we have found a working solution. However, consider the case “???”. If we apply the previous solution, the resulting string would be “CHEFAAA”, whereas the correct solution should be “AAACHEF” because it is lexicographically smaller. We can fix this easily by iterating the string S backwards (the previous lemma and theorem would still apply) so that all occurences of "CHEF"s are “as to the right as possible”.
Here is the pseudocode of the final solution.
for i = N-3; i ≥ 1; i--:
if can_replace(S[i-3.. i], "CHEF"):
replace(S[i-3..i], "CHEF")
for i = N-3; i ≥ 1; i--:
if S[i] == '?':
S[i] = 'A'
The time complexity of this solution is O(N).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.