The HackerRank Simple Text Editor problem asks us to implement a basic text editor. The editor initially contains an empty string, s. We must make sure that the text editor can perform operations of the following types:

1. append(W) - Append string W to the end of s.
2. delete(k) - Delete the last k characters of s.
3. print(k) - Print the kth character of s.
4. undo - Undo the last operation of type 1 or 2, reverting s to the state it was in prior to that operation.

The input is a string where the first line contains an integer representing the total number of operations to perform on the text editor.

Each of the subsequent lines of the input string define an operation to be performed. Each operation starts with an integer that specifies the type of operation to perform. If the operation requires an argument, the operation integer is followed by a space-separated argument. If the integer is 1 and the argument beside it is abcd, then we will append abcd to the empty string S, giving us abcd for s.

Pseudo code solution

1. Convert multi-line input string to an array.
2. Define an empty string s to represent the contents of the text editor.
3. Define a stack data structure to keep a history of changes made to the text editor.
4. Push the empty string s onto the stack.
5. Convert the first character of the input string to an integer, getting the number of queries that will be performed.
6. Create a loop that loops until the total number of queries is reached.
   • Get the operation integer and the possible argument for each operation defined in the input string.
   • If the operation is of type 1, append argument to s and push s onto the stack.
   • If the operation is of type 2, delete the last k characters from s, defined by the argument. Then, push the new s value onto the stack.
   • If the operation is of type 3, access and print the kth characters in s, defined by the argument.
   • If the operation is of type 4, undo the previous operation by popping from the stack and assigning s to be the value that is now at the top of the stack.

Code solution

function processData(input) {
  const lines = input.split('\n');
  let s = '';
  const stack = [];
  stack.push(s);

  // number of operations
  const q = parseInt(lines[0]);

  for (let i = 1; i <= q; i++) {
    const splitLine = lines[i].split(' ');
    const operation = parseInt(splitLine[0]);
    const argument = splitLine[1];

    switch (operation) {
      case 1:
        // append
        s += argument;
        stack.push(s);
        break;
      case 2:
        // delete last k characters
        s = s.substring(0, s.length - parseInt(argument));
        // or slice: s = s.slice(0 , parseInt(args) * -1); (neg index counts back from end of array)
        stack.push(s);
        break;
      case 3:
        // print kth character
        console.log(s.charAt(parseInt(argument) - 1));
        break;
      case 4:
        // undo last operation of case 1 or 2
        stack.pop();
        s = stack[stack.length - 1];
        break;
    }
  }
}

Test cases

Let's test the processData function above with the following test case.

console.log(
  processData(
    `8
    1 abc
    3 3
    2 3
    1 xy
    3 2
    4
    4
    3 1`
  )
);

The 8 specifies that there will be 8 operations to perform on the text editor. The loop that iterates over the operations starts after this initial value. The input string has the operation of type 3 three times, which means we will get three values printed to the console.

Here is the execution flow:

• 1 abc: append abc to s.
• 3 3: print the 3rd character of s, which is c.
• 2 3: delete the last 3 character of s, which are abc. s is now empty.
• 1 xy: append xy to s, with s now being xy.
• 3 2: print the 2nd character of s, which is y.
• 4: undo the appending of xy. s is now empty.
• 4: undo the deletion of the last 3 character of s. s is now abc.
• 3 1: print the 1st character of s, which is a.

The result is:

c;
y;
a;

At the end of the execution, the string s will contain abc.

Time and space complexity

The Big O time complexity of the solution is linear, or O(n), where n is the number of operations defined in the input string. The solution used one loop that iterated over all the lines with operations in the input string.

The Big O space complexity of the solution is linear, or O(n + 1), where n is the number of operations that will be pushed onto the stack that tracks the operation history, plus 1 for the initial empty string s that is pushed onto the stack at the beginning.