Calculating space complexity of string compression - Cracking the coding interview

Question

I am trying to understand space complexity of the following piece of code. The code compresses Strings from "aabbbb" to "a2b4". The question is Question 5, Chapter 1 from Cracking the coding interview version 5 (2013) and the code is taken from the solutions

 public static String compressBetter(String str) {
    int size = countCompression(str);
    if (size >= str.length()) {
        return str;
    }
    StringBuffer mystr = new StringBuffer();
    char last = str.charAt(0);
    int count = 1;
    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) == last) {
            count++;
        } else {
            mystr.append(last);
            mystr.append(count);
            last = str.charAt(i);
            count = 1;
        }
    }
    mystr.append(last);
    mystr.append(count);
    return mystr.toString();
}

where

public static int countCompression(String str) {
    if (str == null || str.isEmpty()) return 0;
    char last = str.charAt(0);
    int size = 0;
    int count = 1;
    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) == last) {
            count++;
        } else {
            last = str.charAt(i);
            size += 1 + String.valueOf(count).length();
            count = 1;
        } 
    }
    size += 1 + String.valueOf(count).length();
    return size;
}

According to the author compressBetter has O(N) space complexity. Why is that not O(1)? In every run of countCompression, we hold last, size and count and similar for compressBetter (holds countCompression variables plus mystr, last, count. My understanding of space complexity is "how much memory the algorithm needs/holds at any time". In other words space complexity unlike time complexity is not cumulative.

Note that the author considers in the book only what people refer as "auxiliary space complexity" (without the space needed to store input) as in the example above. Also, afaik there is no entry in the errata of the book on this.

UPDATE: My source of confusion was from the following example (Question 1.1 in the same book)

public static boolean isUniqueChars2(String str) {
  boolean[] char_set = new boolean[256];
  for (int i = 0; i < str.length(); i++) {
    int val = str.charAt(i);
    if (char_set[val]) return false;
    char_set[val] = true;
  }
  return true;
}

which is O(1) despite a 256 boolean array allocation - I thought allocations don't matter in calculating space complexity. But in reality it's O(1) because the space needed is constant and independent of the input size (unlike the mystr Stringbuffer).

You are holding a StringBuffer that, potentially, could have a size proportional to the String's one. Can it be the reason? — Andrea

Eran Eran · Accepted Answer · 2018-03-06T13:16:23

You are asking about the space complexity of compressBetter, which includes a call to countCompression, but also performs additional work.

While the space complexity of countCompression is indeed O(1), compressBetter has linear space complexity (i.e. O(N)) in the worst case (where no two consecutive characters of the input String are equal), since it produces a StringBuffer of 2N characters in that case.

Calculating space complexity of string compression - Cracking the coding interview

2 Answers