Check if a string can be obtained by a sequences of insertion of "abc"

Question

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?

Algorithm:

    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
            stck.pop
            stck.pop
        else:
            stck.push(c)
            
    return true if and only if stck is empty

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.