I have been taking the test on Codility, and trying this exercise:

Also, given string S = "ABCBBCBA" the function may return "", because one possible sequence of transformations is:

Finally, for string S = "BABABA" the function must return "BABABA", because no rules can be applied to string S.

Write an efficient algorithm for the following assumptions:

the length of string S is within the range [0..50,000]; string S is made only of the following characters: "A", "B" and/or "C".

Here is the code that I tried with a score of 83:

public String solution(String S) {
    
    boolean notAA = false;
    boolean notBB = false;
    boolean notCC = false;

    while(S.length()==0 || true){
        if (S.contains("AA")){
            S = S.replace("AA", "");
        } else {
           notAA = true;
        }

        if(S.contains("BB")){
            S = S.replace("BB", "");
        } else {
            notBB = true;
        }

        if(S.contains("CC")){
            S = S.replace("CC", "");
        } else {
            notCC = true;
        }

        if(notAA && notBB && notCC){
            break;
        }
    }
    return S;
}

I could not obtain the 100% score because of this:

even_palindrome1 big palindrome of even length

✘WRONG ANSWER got CACABACABABCBACBACBA.. expected ""

Codility doesn't show me the string example or any other information.

I was reading and reviewing but I still do not understand why I am not getting the right output. My assumption is when I delete the first combination of letters, the string needs to be in a specific state or a specific combination of letters to work correctly and the problem is the palindrome even string.

But, if my assumption is correct, I don't really understand the real cause or root reason for this.

Thanks in advance for your help.

CodePudding user response：

You should reset notAA, notBB and notCC inside your loop.

Consider, for example, ABCCBA. In your first pass, notAA and notBB are set to true, leaving ABBA. In the second pass, notAA and notCC are set to true, leaving AA. Your program would then break out with an available pair because all three conditions are set to true.

CodePudding user response：

You have to set notAA, notBB and notCC to false inside the loop, not before it. The way you are doing it, you find all three, you end the loop.

• Say S is ABCCBA.
• You set notAA and notBB to true, because AA and BB cannot be found; then you replace CC, giving you ABBA.
• Next loop, you set notAA to true again, remove BB, producing AA, and set notCC to true. Now all three are true (since notBB remained true since the first iteration), and you break the loop.
• The result is AA, which should have reduced further; but because the program thought there was no AA, but it appeared after notAA was set, you get the wrong value.

In fact, this can be simplified: you just need a single flag changed, which starts before the loop as true; then use while (changed). At the top of the loop, set it to false, and set it to true every time you successfully replace a substring. You do not need three separate ones, since they all do effectively the same job.