I went with a completely different approach:
! iterate over our string. Whenever you hit a non-empty, check if the next N are also possible to be a # (N being the first element of our sequence) and that the N+1th isn't a #. If they are, we can truncate the first N+1, the first element of our sequence, and recurse. If you hit a #, you know that the first element has to start here at the latest, so you can break. With this method, memoization is enough to get part 2 down to 25 ms. To make the memoization more efficient you can also truncate all the way up to the next non-empty when recursing. !<