CODEWITHSUNDEEP
pythonalgorithmtime-complexityasymptotic-complexityspace-complexity
edmamerto
edmamerto

Reputation: 8165

Trying to understand the space complexity of concatenated string output

I had this problem in a coding interview:

# AAABB should return A3B2

This is a classic algorithm interview question. I said that I can solve this in O(n) time and O(1) space.

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

I understand that O(n) space means that it grows proportionally with the size of input. So I was thinking that O(n) space would look something like [(A,3),(B,2)].

I am under the impression that A3B2 is in O(1) space since it's not being split up into multiple strings.

I now realized that n == len(s) and my output grows un-proportionally (less) with my input size, so is it correct to say that space is O(log n)?

Upvotes: 1

Views: 2183

Answers (1)

Davis Herring
Davis Herring

Reputation: 40013

The length of the output string you store must be counted. In the worst case (no consecutive characters match), it’s actually twice as long as the input. So clearly it’s O(n) in general: it would only be asymptotically better if somehow you knew that long inputs always contained very long runs. (In the best case, all characters are the same, and the length of the one number is O(log n).)

That said, it’s sometimes useful to consider your output as a stream (like print), and then your space complexity (for count and perhaps the current input character) is constant. Of course, even then it’s technically logarithmic, since the number of bits needed to store count is, but that’s often disregarded in practical analyses.

Upvotes: 5

Related Questions