Checking if a string of "a" and "b" can be reduced to empty if duplicates occur consecutively

def solveit(string):
    def remove(items, index):
        if index == 0:
            return items[1:]
        elif index == len(items) - 1:
            return items[:-1]
        else:
            # We delete a central element, and join the two surrounding
            # elements (each at least size 1) into a 'True'
            return (*items[0:index - 1], True, *items[index + 2:])

    @cache
    def recurse(items):
        # An empty list returns True
        if len(items) == 0:
            return True
        # A list of length 1 returns True if the group is bigger than 1
        if len(items) == 1:
            return items[0]
        # See if removing any "True" item and recursing works.
        return any(recurse(remove(items, index))
                   for index, item in enumerate(items) if item)

    # Convert the input into a tuple of False and True, where False indicates
    # a group of size 1, and True indicates a group of size 2 or more
    result = []
    for key, values in itertools.groupby(string):
        result.append(len(list(values)) > 1)
    return recurse(tuple(result))

Given your setup, shouldn't your data structure just be a list of positive integers indicating the sizes of the groups? It really doesn't matter, for the purposes of your problem, if the first group is a list of 'a's or 'b's.

The operation you can perform on your list is to remove an element that is larger than 2, and combining the two elements (if they exist) on either side? Hence the example you gave above is [1, 1, 2, 3, 2] -> [1, 4, 2] -> [3] -> [].

In fact, all that really matters is whether a group is size 1 or size bigger than 1. [1, 1, 2+, 2+, 2+] -> [1, 2+, 2+] -> [2+] -> []

Because you must be able to branch through the possibilities, I don't think a stack used like this will work.

The following actually works for any number of different characters, but is not O(N) due to search approach.

The approach I use below rewrites your string using RUN-LENGTH ENCODING. (Thus, for example, 'babbbaaabb' becomes 1b,1a,3b,3a,2b.)

It then does a DFS (depth-first search) via all the elements with a multiple greater than 1. It's a little inefficient (multiple copying).

It can be substantially simplified if (as in your case) there are only two possible characters (see Frank Yellin's post) and whether successive element counts are 1 or greater-than-1 (so you could reduce it to binary). However, for generality, I've coded as if there can be any number of different characters.

The implementation below is in C++ (sorry!!! my python's not up to it yet!), but I expect a decent python coder can translate it.

If you set debug=false then it will just output true or false. If you set debug=true then it will show you all the routes it might check. (In the example below the first route would work immediately, but that's not a given).

Edge cases: empty string -> true; single character -> false.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool debug = true;
//bool debug = false;

//==============================================================================

struct RLE
{
   int n;
   char c;
};

//==============================================================================

ostream &operator << ( ostream &out, const vector<RLE> &R )
{
   for ( auto r : R ) out << r.n << r.c << " ";
   return out;
}

//==============================================================================

vector<RLE> runLengthEncode( const string &s )
{
   vector<RLE> result;
   if ( s.empty() ) return result;
   int p = 0, q;
   while ( true )
   {
      char c = s[p];
      q = s.find_first_not_of( c, p );
      if ( q == string::npos )
      {
         result.push_back( { s.length() - p, c } );
         break;
      }
      else
      {
         result.push_back( { q - p, c } );
         p = q;
      }
   }
   return result;
}

//==============================================================================

bool dfs( const vector<RLE> &R )
{
   if ( debug )
   {
      cout << "Testing " << R << '\n';
      if ( R.size() == 0 ) cout << "YEAH!!!!!\n";
   }
   else
   {
      if ( R.size() == 0 ) return true;
   }

   for ( int i = 0; i < R.size(); i++ )
   {
      if ( R[i].n > 1 )
      {
         auto RR = R;
         RR.erase( RR.begin() + i );
         if ( i > 0 && i < RR.size() && RR[i-1].c == RR[i].c )    // combine RLEs from two sides
         {
            RR[i-1].n += RR[i].n;
            RR.erase( RR.begin() + i );
         }
         if ( dfs( RR ) ) return true;
      }
   }

   return false;
}

//==============================================================================

int main()
{
   string s = "babbbaaabb";
// string s = "aababaabb";
// string s = "abbaab";
// string s = "a";
// string s = "";
   bool ok = dfs( runLengthEncode( s ) ) << '\n';
   if ( !debug ) cout << boolalpha << ok << '\n';
}

Output (with debug=true, showing all routes):

Testing 1b 1a 3b 3a 2b 
Testing 1b 4a 2b 
Testing 3b 
Testing 
YEAH!!!!!
Testing 1b 4a 
Testing 1b 
Testing 1b 1a 5b 
Testing 1b 1a 
Testing 1b 1a 3b 3a 
Testing 1b 4a 
Testing 1b 
Testing 1b 1a 3b 
Testing 1b 1a 

Output with debug=false:

true

Credit to Frank for his answer outlining the simplification to coalesce consecutive characters into single/multi character groups, forming a bitstring.

Building on this, I think its beneficial to compare this problem to classic lattice problems like checking balanced parenthesis or shifting / reducing from values on stack. Each single character group needs to combine with a group either to its left or to its right. You can imagine this as the choice of either shifting the group onto the stack, or reducing the top of the stack by removing all groups of the same character (requiring 2+ characters total). There's a bit more to it than that; we have to lay out some rules for when we're allowed to do each operations, but it sets the general idea.

Personally, I've been visualizing this graphically in my head as a lattice in the upper half plane, where the y-axis is my stack size, and the x-axis is by character group index. If I push a group onto the stack, I'd go one unit right and one unit up. We're trying to find a path from (0, 0) to (G, 0), where G is the number of character groups.

To simplify details and to mirror my code, I need to clarify some terminology. From here on, when I mention "reducing", I mean implicitly shifting the current group and then immediately reducing the top two groups of the stack. Besides being more compact, this also eliminates some redundancy in our stack state and makes it significantly easier to track the state of groups. Secondly, when I say a group is "stack-matching", I mean that the character(s) of that group match the character(s) of the group at the top of the stack. Lastly, when I say a group is "reducible" or can be reduced, I mean that (a) the stack is not empty and (b) the current group is stack-matching.

With that, we can start to build our DP table. It will have 3 dimensions: the group index, a boolean for stack-matching, and the stack size. For the single character group, we have three rules:

• if reducible, try reducing current group
• if reducible, try discarding current group
• if not reducible, try shifting current group

The first and last are fairly self-explanatory. The second rule is a result of how I've defined "reduce" above. We want our stack to alternate character groups ("a", "b", "a", ...), but some solutions would require combining 3+ groups at once, so we emulate this by discarding the current stack-matching group, leaving the top of the stack alone to combine 1:1 with a matching group sometime later.

For the multi character group case, we also have three rules:

• if reducible, try reducing current group
• unconditionally, try discarding the current group
• if not reducible, try shifting current group

Again, the first and last rules are self-explanatory (they are the same as before). The second rule is again an artifact of how we've defined reduction- we require exactly two groups, but in the case of a multi character group, the group could itself be eliminated without the need to combine with any other groups prior (via shifting and/or reducing).

In each of these six cases, we need to be careful to track whether the next group will be stack-matching based on our operations, but luckily due to the way we defined our reduce operation, we guarantee the stack alternates characters, so we can trivially determine stack-matching in each case without auxiliary data or expensive computation.

Here is what it looks like implemented recursively with memoisation:

from itertools import groupby
from functools import cache

def solve(string):
    bitvec = [len(list(group)) > 1 for key, group in groupby(string)]
    
    @cache
    def is_solvable(index, is_matching, stack_size):
        if index == len(bitvec):
            return stack_size == 0

        is_multi = bitvec[index]
        is_reducible = is_matching and stack_size > 0

        # (shift and) reduce group
        if is_reducible:
            if is_solvable(index + 1, True, stack_size - 1):
                return True

        # discard group
        if is_multi:
            # group doesn't need another group to combine with
            if is_solvable(index + 1, not is_matching, stack_size):
                return True
        else:
            # emulate 3+ way deferred combine / reduce
            if is_reducible and is_solvable(index + 1, False, stack_size):
                return True

        # shift group
        if not is_reducible:
            if is_solvable(index + 1, False, stack_size + 1):
                return True
                
        return False

    return is_solvable(0, False, 0)

On the average case, the code runs about 10x faster than the recursive solution provided in Frank's answer. When I inspected a handful of such inputs, I saw that the numbers of times the inner function gets called is within a small factor of G (the number of character groups). This is because I've ordered the rules to try the options that reduce stack size greedily first.

On the worst case, the code runs at least couple orders of magnitude faster. For the string aabaabbabbabbababababababababababaabbaabbabaababbabb I measured 0.0003595 vs 0.0477324 seconds, averaged across 50 samples. This is explained by the fact that the time complexity of my DP solution is O(G^2), whereas the recursion in the other answer has exponential worst-case time complexity. Also note that the worst-case is always when the result is False, meaning that the entire search space must be explored.

Statistically, strings that yield a False are extremely rare as the string length grows longer and longer. This means that in practice, the worst-case becomes less and less likely, and the average case (for both) tends to be roughly linear in G. I had significant difficulty randomly generating long false strings without just outright "constructing" them (obviously with some added bias). Again though, this may not matter for real-world data.

I'll keep thinking about the problem and see if I can come up with any insights that could lead to the O(n) desired solution.