Strings vs Arrays in JS

Hey guys, recently I came across the "Design a Text Editor" task on leetcode (hard level). In short, we need to implement the following:

• Add text to where the cursor is
• Delete text from where the cursor is (simulating the backspace key)
• Move the cursor either left or right

Rules for the code (as usual):

1. Choose the right names for variables
2. Choose the right loop statements: for, while, forEach, reduce etc.
3. Avoid excess conditions and comparisons for edge cases
4. Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity

Strings - version 1

The first thing that might come to mind is manipulating strings.

class TextEditor {
  cursorPosition = 0;
  text = '';

  /**
   * @param {string} text
   * @return {void}
   */
  addText = (text) => {
    this.text =
      this.text.substring(0, this.cursorPosition) + text + this.text.substring(this.cursorPosition);
    this.cursorPosition += text.length;
  };

  /**
   * @param {number} k
   * @return {number}
   */
  deleteText = (k) => {
    const deletedCount = Math.min(this.cursorPosition, k);

    this.text =
      this.text.substring(0, this.cursorPosition - deletedCount) + this.text.substring(this.cursorPosition);
    this.cursorPosition = this.cursorPosition - deletedCount;

    return deletedCount;
  };

  /**
   * @param {number} k
   * @return {string}
   */
  cursorLeft = (k) => {
    this.cursorPosition = Math.max(0, this.cursorPosition - k);

    return this.text.substring(this.cursorPosition - 10, this.cursorPosition);
  };

  /**
   * @param {number} k
   * @return {string}
   */
  cursorRight = (k) => {
    this.cursorPosition = Math.min(this.text.length, this.cursorPosition + k);

    return this.text.substring(this.cursorPosition - 10, this.cursorPosition);
  };
}

Check it out on leetcode.

Sometimes it fails by time limits. But will have a good spot by memory consumption.

Arrays - version 1

Looking at the best time-consuming solution, we will see code that manipulates arrays. And memory usage is good enough too.

Sample code:

var TextEditor = function () {
  this.left = [];
  this.right = [];
};

TextEditor.prototype.addText = function (text) {
  for(var i = 0; i < text.length; i++) {
    this.left.push(text[i]);
  }
};

Conclusion: Big difference in time and almost nothing difference in memory. Why? Let's dive deep into the JS engine.

JS engine

Firstly it depends on the amount of data, in our case we have 2 * 104 operations which is a lot. Also, it depends on the implementation of the JS engine.

The String
It is a primitive data type and as a rule, primitives are immutable, so strings don't change when the developer manipulates the strings. How it works:

let text = 'string';
text += ' changed';
console.log(text);

In the console, we will see the string changed which means our text variable is mutable. But under the hood, the engine just creates a third empty string and copies the values of both strings to it, and assigns the result to the text variable. Therefore, we have mutable the text variable and immutable string data type.

Let's visualize this algorithm:

1. Create an empty range in memory for the new string. To concatenate our two strings we need to save 14 chars (by 2 bytes).

   _

   _

   _

   _

   _

   _

   _

   _

   _

   _

   _

   _

   _

   _

2. Copy the first string

   s

   t

   r

   i

   n

   g

   _

   _

   _

   _

   _

   _

   _

   _

3. Copy the second string

   s

   t

   r

   i

   n

   g

   c

   h

   a

   n

   g

   e

   d

4. Assign the result to the var

   text =

   s

   t

   r

   i

   n

   g

   c

   h

   a

   n

   g

   e

   d

5. Frees memory that was used to hold "string" and " changed" strings.

As you see it takes additional operations than it really needs (it copies each string fully), and at some point in time we have two times more memory. Just open the console and paste the following code:

let str = '';
console.time('experiment');

for (let index = 0; index < 100_000_000; index++) {
    str += 'w';
}

console.timeEnd('experiment');
console.log(str.length);

In my case, it took 9.5 sec. Now try to paste the following one:

let str = [];
console.time('experiment');

for (let index = 0; index < 100_000_000; index++) {
    str.push('w');
}

console.timeEnd('experiment');
console.log(str.length);

In my case, it took 886 milliseconds 😃 great!
Note: This case is only appropriate for inserting in the end of the sequence and if you will try something like:

let str = [];
console.time('experiment');

for (let index = 0; index < 500_000; index++) {
    const middleIndex = Math.floor(str.length / 2);
    str.splice(middleIndex, 0, 'w');
}

console.timeEnd('experiment');
console.log(str.length);

it will take a longer time than with strings 🤯.

The Array
It is happening because in "JS engines" the arrays are implemented like dynamic arrays. The ECMAScript standards don't strictly define how the arrays should work, and because of this, we may encounter different implementations in the JS engines. And also JS engines have different implementations for dense and sparse arrays. Example in v8 for elements. And a few links about dynamic arrays:
Dynamic Array (data structure)
How do Dynamic arrays work?

Thus, in our case, array-based solutions will only be faster than string-based ones if only the push and pop methods are used. So it will look like manipulating two arrays.

class TextEditor {
  left = [];
  right = [];

  /**
   * @param {string} text
   * @return {void}
   */
  addText = (text) => {
    this.left.push(...text);
  };

  /**
   * @param {number} count
   * @return {number}
   */
  deleteText = (count) => {
    let deletedCount = 0;

    while (this.left.length && deletedCount < count) {
      this.left.pop();
      deletedCount++;
    }

    return deletedCount;
  };

  /**
   * @param {number} movesCount
   * @param {'toLeft' | 'toRight'} direction
   */
  moveCursor = (movesCount, direction) => {
    let actualMoves = 0;
    let currentElement = null;
    let from;
    let to;

    if (direction === 'toLeft') {
      from = this.left;
      to = this.right;
    } else if (direction === 'toRight') {
      from = this.right;
      to = this.left;
    }

    while (from.length && actualMoves < movesCount) {
      currentElement = from.pop();
      to.push(currentElement);
      actualMoves++;
    }

    return this.left.slice(-10).join('');
  };

  /**
   * @param {number} movesCount
   * @return {string}
   */
  cursorLeft = (movesCount) => {
    return this.moveCursor(movesCount, 'toLeft');
  };

  /**
   * @param {number} movesCount
   * @return {string}
   */
  cursorRight = (movesCount) => {
    return this.moveCursor(movesCount, 'toRight');
  };
}

Check it out on leetcode.

When we work with "big strings" that we decided to replace with the array we should remember the limit for the range. It is worth noticing that different algorithms exist to optimize manipulating strings and one of the most efficient is rope by splitting strings into multiple smaller chunks.

Sources:
ChatGPT
Efficient string building in javascript
How Arrays are Implemented in JavaScript

Let me know your thoughts in the comment section below! 😊