Let $a$ initially be an empty string. One can transform $a$ into $b$ in the following way: $a$ becomes $a_{left}+$"$abc$"$+a_{right}$, where $a=a_{left}+a_{right}$ in a prior state. $a_{left}$ or $a_{right}$ can be the empty string. Given a string $b$, check if it is valid, i.e. check if it can be obtained from $a=$"" by applying the transformation described above zero or more times.

I have written an algorithm, and I am almost 100% sure it is correct. I draw this conclusion almost exclusively from having run the algorithm on many test cases. I am, however, unable to prove the correctness. In other words, I am unable to understand how it works at a deep level. Can you help me with that? Can you clearly and thoroughly prove the correctness?


    let stck be an empty stack of characters
    for each character c in the string b:
        if c=="c":
            if length of stack is strictly less than 2:
                return False
            if the second to last character is not "a" OR the last character is not "b":
                return False
    return true if and only if stck is empty

1 Answer 1


Congratulation, your algorithm works fast and correctly like magic. However, why is it correct?

Claim: A string $s$ is valid iff either $s$ is empty or the two letters to the left of the leftmost occurrence of $c$ in $s$ is "$ab$" and $s$ with that "$abc$" removed is still valid.

Proof: "$\impliedby$" is by definition.

"$\implies$". Let $s$ be a valid string. If $s$ is empty, of course. Assume $s$ is not empty. $s$ was obtained by a series of insertion of "$abc$". Instead of $a, b, c$, we can imagine that each $a$ is an apple, each $b$ is a banana, and each $c$ is a cherry. Each fruit is different from another. Now we can identify and track each letter in $s$, without loss of generality.

Consider the insertion $L$ that inserted $c_L$, the leftmost cherry in $s$.

I claim that all insertions that happened after $L$ must insert "$abc$" to the right of $c_L$. Otherwise, whichever insertion happening after $L$ that inserted to the left $c_L$ will leave some cherry, say, $c_0$ to the left of $c_L$. Notice that any insertion does not change the left-right order of existing letters/fruits. No matter what happened later, $c_0$ would have remained to the left of $c_L$, which contradicts the fact that $c_L$ is the leftmost $c$ in $s$.

Hence the letters to the left of $c_L$ would never change after $L$ had been performed. That means, the two letters immediately to the left of $c_L$ in $s$ must be "$ab$". The substring "$abc_L$" is the first occurrence of $abc$ in $s$.

Now imagine we repeat the series of insertions that produced $s$, starting from the empty string, with one exception: when it is time to repeat $L$, we will skip it instead. Since all later insertions inserted to the right of $c_L$, we can see that this new execution series will yield $s$ without the substring "$abc_L$". $\quad\checkmark$

Correctness of your algorithm follows from the claim above.

  • Suppose $s$ is valid.
    When the algorithm encounters the first $c$, i.e., the leftmost "$c$", "$c_L$" of $s$, the claims tells us that "$ab$" must be on the top of the stack. The algorithm then "removes" the substring "$abc_L$". Ignoring this substring, the algorithm had been behaving and will be behaving exactly the same as if the input had been $s$ with "$abc_L$" removed. So, by induction on the length of $s$ and that $s$ accepts the empty string, we see that $s$ will be accepted by the algorithm.

  • On the other hand, if $s$ is accepted by the algorithm, it is easy to see that $s$ is valid.

Exercise. Show that given a valid string $s$ and any substring "$abc$" in it, $s$ with that substring removed is still valid.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.