Why is the run time exponential in the length of the string of a's? It seems like it should be at most O(n^3). 2^n is the number of subsets of the string of a'

Why is the run time exponential in the length of the string of a's? It seems like it should be at most O(n^3). 2^n is the number of subsets of the string of a's with no contiguity requirements. Nothing like this number of possible matches should need to be checked. What am I missing?