I have been taking the test on Codility, and trying this exercise:
https://app.codility.com/programmers/trainings/4/disappearing_pairs/
A string S containing only the letters "A", "B" and "C" is given. The string can be transformed by removing one occurrence of "AA", "BB" or "CC".
Transformation of the string is the process of removing letters from it, based on the rules described above. As long as at least one rule can be applied, the process should be repeated. If more than one rule can be used, any one of them could be chosen.
Write a function:
class Solution { public String solution(String S); }
that, given a string S consisting of N characters, returns any string that can result from a sequence of transformations as described above.
For example, given string S = "ACCAABBC" the function may return "AC", because one of the possible sequences of transformations is as follows:
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.
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.
S
is ABCCBA
.notAA
and notBB
to true
, because AA
and BB
cannot be found; then you replace CC
, giving you ABBA
.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.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.