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

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


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.