title: efficient string char elimination in python
body: <p>I have a python for loop over a string, that have to decide char-by-char if the current char should stay or be removed.</p>
  
  <p>Let's say I have a function <code>fun(character,state)</code> which receives a char, and some state parameter, and returns <code>True</code> if the char should be kept, and a new <code>state</code>. for example:</p>
  
  <pre><code>def fun(c,state):
      if state%5==0:
          return False, state+1
      else:
          return True, state+2
  </code></pre>
  
  <p>I have two ideas how to iterate (sequentially) over the string with this function, but I can't decide between them (or others) in terms of <strong>runtime complexity</strong> and <strong>space usage</strong> tradeoff:</p>
  
  <h2>Option 1:</h2>
  
  <pre><code>def option1(string):
      state = 0
      i =0
      while i&lt;len(string):
          answer, state = fun(string[i],state)
          if not answer:
               string = string[:i]+string[i+1:]
          else:
              i+=1
      return string
  </code></pre>
  
  <h2>Option 2:</h2>
  
  <pre><code>def option2(string):
      result  = ''
      state = 0
      for c in string:
          answer, state = fun(c,state)
          if answer:
               result+=c
     return result
  </code></pre>
  
  <p>Does anyone has a better approach/ solution?</p>
  
  <hr>
  
  <p><strong>edit:</strong> some timing results:</p>
  
  <p>on a long string ( 67976 chars) the results are:</p>
  
  <ul>
  <li>option1 - 205 ms</li>
  <li>option2 - 46 ms</li>
  </ul>
  
  <p>looks like eliminating the i'th char with <code>string[:i]+string[i+1:]</code> is not a good idea.</p>