×

SIMPLE

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.

This question is marked "community wiki".

16345853
accept rate: 0%

17.4k347486515

 0 What about C???F According to this algorithm it would give CHEFF while lexicographically smaller would be CCHEF answered 21 Jan '13, 09:49 1 accept rate: 0% 1 No, according to this algorithm it would get CCHEF because it iterates from the end of the string. See the pseudocode. (21 Jan '13, 10:07)

What is wrong in this code?? it is giving right answers for all the tests cases.

# include<iostream>

using namespace std;

int main() { int t; cin>>t;

while(t--) { int i=0,j=0,c,k,l; string s=""; char b[4]={'C','H','E','F'}; cin>>s; l=s.length(); while(i<l-3) { c=0; for(j=0;j<4;j++) { k=3; char p=s.at(i+j); if(p=='?') s.replace(i+j,1,"A"); p=s.at(i+j); if(p=='A' || p==b[j] || p==b[k]) c++; k--; } if(c==4) { s.replace(i,4,"CHEF"); i+=4; } else i++; } cout<<s<<"n"; } return 0; }

6115
accept rate: 0%

 0 Are we iterating from the end of the string so that we can get lexicographically small string ? 1) If we need to find lexicographically large string then from when should we start to loop ? (from start or from the end) 2) How would we tackle the problem if we have CAEHEH instead of CHEF ? answered 17 Jun '13, 17:19 3★geekguy 1●2●2 accept rate: 0%
 0 WHY we iterating Iit from the end of the string ? answered 11 Apr '15, 20:03 3★gether 1 accept rate: 0%
 0 Hi.. I would like to know for which testcases my Solution is failing. From my end, I could see that all testcases are passing. Can someone please help on this ? https://www.codechef.com/viewsolution/9047102 ????CIELIS???E? --> CHEFCIELISACHEF ????CIELISOUR???F --> CHEFCIELISOURCHEF T?KEITE?SY --> TAKEITEASY ???????? --> CHEFCHEF ??????? --> AAACHEF C???F --> CCHEF answered 31 Dec '15, 14:19 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×12,235
×801
×738
×8
×8

question asked: 21 Jan '13, 00:25

question was seen: 17,182 times

last updated: 31 Dec '15, 14:56