Here is a whiteboarding problem that may come up in interviews.

You are given a string. Implement a function to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, the function should return the original string. For example, the string aabc would remain aabc because a2b1c1 is larger than the original.

This is a pretty simple problem to solve. Here is a basic implementation:

var compressedString = function(str) {  
  if (str.length < 3) return str;

  var compressedStr = '';
  var prevChar = str.charAt(0);
  var count = 1;

  for (var i = 1; i < str.length; i++) {
    if (str[i] !== prevChar) {
      compressedStr += prevChar + count;
      prevChar = str[i];
      count = 1;
    } else {
      count++;
    }
  }
  compressedStr += prevChar + count;

  return compressedStr.length >= str.length ? str : compressedStr;
};

That was my initial stab at the solution. I was then curious to see how others went about it. While I was doing research, I learned something new. The string concatenation happening within the for-loop using compressedStr += prevChar + count can potentially operate in O(n²) time, depending on the environment; some browsers have optimizations to make string concatenation more performant.

In JavaScript, strings are immutable—they cannot be changed. As a result, doing concatenation using += will create a copy of the string by iterating through each character one at a time (O(n)), and then appending the new string to the end. So because the string concatenation happens in linear time, and you have to iterate up to n characters with the for-loop, that results to O(n²).

If you have a large string and time is important, then a data structure like a StringBuffer would give you O(n) time. In a nutshell, a StringBuffer is an array that progressively collects each character of a string, and then at the end, it joins all the characters as a string. Thus, the concatenation only happens once at the very end instead of each time a new character is added. That does mean you end up with O(n) space though.

But wait, StringBuffer doesn't exist in JavaScript! Well, we can create a basic version of a StringBuffer. Check it:

var compressedString = function(str) {  
  if (str.length < 3) return str;

  var compressedStrArray = [];
  var index = 0;
  var char = str.charAt(0);
  var count = 1;

  for (var i = 1; i < str.length; i++) {
    if (str[i] !== char) {
      index = setChar(compressedStrArray, index, char, count);
      char = str[i];
      count = 1;
    } else {
      count++;
    }
  }
  setChar(compressedStrArray, index, char, count);
  var compressedStr = compressedStrArray.join('');

  return compressedStr.length >= str.length ? str : compressedStr;
};

var setChar = function(array, index, char, count) {  
  array[index++] = char;
  array[index++] = count;
  return index;
};

One optimization included is using the helper function, setChar, to append characters to the array representing the StringBuffer. The Array.prototype.push method could have been used to append new characters to the StringBuffer, but referencing an index is faster.

So is it still "safe" to use += concatenation? Absolutely, but you need to consider the environment where your code is running. Recent browsers will have optimizations for +=. Also, if you are doing a one-time concatenation and not concatenating within a loop, feel free to use +=.