title: repeatedly remove occurrences of substring until main string is empty
body: <p>So I have the stack and needle:</p>
  
  <p><code>stack = 'lllolollololollllolol'</code></p>
  
  <p><code>needle = 'lol'</code></p>
  
  <p>If I remove one <code>needle</code> from <code>stack</code> each time, with the right order, <code>stack</code> can be cleared so it's empty at the end.
  For example, each time, the <code>lol</code> in bold is removed (notice that another <code>needle</code> can be further created after the removal):</p>
  
  <p>lllolollolololll<strong>lol</strong>ol</p>
  
  <p>lllolollolololl<strong>lol</strong></p>
  
  <p>lllolol<strong>lol</strong>ololl</p>
  
  <p>llollolo<strong>lol</strong>l</p>
  
  <p>llol<strong>lol</strong>ol</p>
  
  <p>l<strong>lol</strong>ol</p>
  
  <p><strong>lol</strong></p>
  
  <p><em>clear</em></p>
  
  <p>To find a route like above, the only way I came up with using Python is to use regex (finditer) to find all the <code>needles</code> in the <code>stack</code>, and use recursion to explore all the possible removing combinations to find the ones that can make <code>stack</code> empty. But I know that this is not efficient at all.</p>
  
  <p>Is there a more efficient way to find at least 1 way to remove <code>needle</code> to empty <code>stack</code> using Python?</p>
  
  <p>I found this topic:
  <a href="https://stackoverflow.com/questions/28643004/remove-occurences-of-substring-recursively">Remove occurences of substring recursively</a>
  But I'm not sure if it 100% apply to my case.</p>
  
  <p>Thanks!</p>
  
  <p>Below is the code I came up with (bad complexity I know..):</p>
  
  <pre><code>def answer(chunk, word):
      if chunk.find(word) != -1:
          occ = [m.start() for m in finditer('(?='+word+')', chunk)]
          for o in occ:
              new = chunk[:o] + chunk[o + len(word):]
              answer(new, word)
      else:
          result.append(chunk)
          result.sort()
          return chunk
  ...
  #So all the shortest "leftover stack" after the removal are stored in list 
  #"result". These include empty or non-empty outputs depending on how 
  #the removal was executed.
  </code></pre>