Issue in making a String Algorithm

Question

Given a string made up of 'a' and 'b' only,the operation that is allowed is to remove a substring of "abb" if present from the string. My question is after applying this operation any no of times can i make the string empty. I need a O(n) algorithm.

Example , abbabb-->yes

aabbbb->yes since aabbbb->abb->empty

aaabbb->no since aaabbb->aab

All that i can think upto now is an O(n^2) algorithm in which i sucessively find the position of the substring using substr() or find() and then remove it until string not empty or not found a "abb" in it.

Answer 1

Here is an example of what I suggested in the comment:

for i = 0 to word.length-1
    if word[i] == 'b'
        if stack.empty() //no corresponding a
            return false
        if stack.top() == 'a' //first b after an a
            stack.push('b')
        else                  //second b after an a
            stack.pop()       //pop last two letters
            stack.pop()
    else
        stack.push('a')
return stack.empty()

There might be some boundary conditions that needs to be checked, and of course at any point pop() fails you need to return false. Seems to be working for the possible inputs that occurs to me.

The point that needs to be mathematically proved, I think, is the part where I commented "second b after an a". With the assumption that stack was empty at the beginning, if I did not miss anything that point looks correct.