## Algorithm

Problem Name: Data Structures - Simple Text Editor

In this HackerRank in Data Structures - Simple Text Editor solutions

Implement a simple text editor. The editor initially contains an empty string, S.

Perform Q operations of the following 4 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 k**th character of S.
4. undo() - Undo the last (not previously undone) operation of type 1 of 2 reverting S to the state it was in prior to that operation.

Example

S = 'abcde'

ops = '1 fg', '3 6', '2 5', '3 7' ,  '4' , '3 4'

operation
index   S       ops[index]  explanation
-----   ------  ----------  -----------
0       abcde   1 fg        append fg
1       abcdefg 3 6         print the 6th letter - f
2       abcdefg 2 5         delete the last 5 letters
3       ab      4           undo the last operation, index 2
4       abcdefg 3 7         print the 7th characgter - g
5       abcdefg 4           undo the last operation, index 0
6       abcde   3 4         print the 4th character - d


The results should be printed as:

f
g
d


Input Format

The first line contains an integer, Q, denoting the number of operations.
Each line i of the Q subsequent lines (where 0 <= i < Q) defines an operation to be performed. Each operation starts with a single integer, t (where t E {1,2,3,4} denoting a type of operation as defined in the Problem Statement above. If the operation requires an argument, t is followed by its space-separated argument. For example, if t = 1 and W = 'abcd' , line

will be 1 abcd.

Constraints

• 1 <= Q <= 10**6
• 1 <= k <= |S|
• The sum of the lengths of all W in the input <= 10**6
• The sum of k over all delete operations <= 2 * 10**6
• All input characters are lowercase English letters.
• It is guaranteed that the sequence of operations given as input is possible to perform.

Output Format

Each operation of type 3 must print the k**th haracter on a new line.

Sample Input

STDIN   Function
-----   --------
8       Q = 8
1 abc   ops[0] = '1 abc'
3 3     ops[1] = '3 3'
2 3     ...
1 xy
3 2
4
4
3 1


Sample Output

c
y
a

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>
using namespace std;

int main() {
string s = "";
int cas;
cin >> cas;
vector < string> prev;
for(int i = 0; i  <  cas; i++){
string t, r;
cin >> t;
if(t != "4") cin >> r;

if(t == "1"){
prev.push_back(s);
s += r;
}
else if( t == "2"){
prev.push_back(s);
s.erase(s.end() - stoi(r), s.end());
}
else if(t == "3"){ cout << s[stoi(r)-1] << endl; }
else {
s = prev.back();
prev.pop_back();
}
}
return 0;
}

Copy The Code &

### #2 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct stack{
char data[1000001];
struct stack *next;
};

int isEmpty(struct stack *top){
return !top;
}

void push(struct stack **top, char *data){
struct stack *newnode = (struct stack*)malloc(sizeof(struct stack));
strcpy(newnode->data, data);
newnode->next = (*top);
(*top) = newnode;
}

void pop(struct stack **top){
if(isEmpty(*top))
return;
struct stack *node = *top;
(*top) = (*top)->next;
free(node);
}

int main() {

int Q;
scanf("%d", &Q);
char s[1000001] = "\0";

struct stack* top = NULL;
push(&top, s);

int options;
while(Q > 0){
scanf("%d", &options);
if(options == 1){
char W[1000001];
scanf("%s", W);
strcat(s, W);
push(&top, s);
}
else if(options == 2){
int K;
scanf("%d", &K);
K = strlen(s) - K;
s[K] = '\0';
push(&top, s);
}
else if(options == 3){
int Kth;
scanf("%d", &Kth);
printf("%c\n", s[Kth - 1]);
}
else if(options == 4){
pop(&top);
strcpy(s, top->data);
}
--Q;
}

return 0;
}

Copy The Code &

### #3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int queries = scanner.nextInt();
Stack < String> stack = new Stack<>();
StringBuilder builder = new StringBuilder();
scanner.nextLine();
for(int i = 0; i  <  queries; i++){
String query = scanner.nextLine();
int operation = Integer.parseInt(query.split(" ")[0]);
switch(operation){
case 1: //append
stack.push(builder.toString());
builder.append(query.split(" ")[1]);
break;
case 2: //delete last K chars
stack.push(builder.toString());
builder.delete(builder.length()-Integer.parseInt(query.split(" ")[1]), builder.length());
break;
case 3: //print kth character
System.out.println(builder.charAt(Integer.parseInt(query.split(" ")[1])-1));
break;
case 4: //undo
builder = new StringBuilder(stack.pop());
break;
}
}
scanner.close();
}
}


Copy The Code &

### #4 Code Example with Javascript Programming

Code - Javascript Programming


function processData(input) {
const [_, ...operations] = input.split("\n");
const records = [];
let str = '';
for(const operation of operations) {
const [operator, value] = operation.split(' ');
switch(operator) {
case '1':
records.push({operator: '1', state: str});
str = str + value;
break;
case '2':
records.push({operator: '2', state: str});
str = str.substr(0, str.length - Number(value));
break;
case '3':
process.stdout.write(str.substr(Number(value) - 1, 1) + "\n");
break;
case '4':
const last = records.pop();
str = last.state;
break;
default:
break;
}
}

return str;
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});

Copy The Code &

### #5 Code Example with PHP Programming

Code - PHP Programming




Copy The Code &

### #6 Code Example with Python Programming

Code - Python Programming


hist = [""]  # stores history of operation. Initially empty string
for i in range(int(input())):
args = input().split()

if args[0] == '1':
hist.append(hist[-1] + args[1])
elif args[0] == '2':
hist.append(hist[-1][:len(hist[-1])-int(args[1])])
elif args[0] == '3':
print(hist[-1][int(args[1])-1])
else:
hist.pop()

Copy The Code &