title: Trying to understand the space complexity of concatenated string output
body: <p>I had this problem in a coding interview:</p>
  
  <pre><code># AAABB should return A3B2
  </code></pre>
  
  <p>This is a classic algorithm interview question. I said that I can solve this in <code>O(n)</code> time and <code>O(1)</code> space.</p>
  
  <pre><code>def compress(s):
  
      output = ''
      count = 1
  
      for i in range(len(s)-1):
          if s[i] == s[i+1]:
              count+=1
          else:
              output = output + s[i] + str(count)
              count=1
  
      output = output +s[i+1] + str(count)
      return output
  
  compress('AAABB') #returns A3B2
  </code></pre>
  
  <p>I understand that <code>O(n)</code> space means that it grows proportionally with the size of input. So I was thinking that <code>O(n)</code> space would look something like
  <code>[(A,3),(B,2)]</code>.</p>
  
  <p>I am under the impression that <code>A3B2</code> is in <code>O(1)</code> space since it's not being split up into multiple strings.</p>
  
  <p>I now realized that <code>n == len(s)</code> and my output grows un-proportionally (less) with my input size, so is it correct to say that space is <code>O(log n)</code>?</p>