Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Implement a simple text editor. The editor initially contains an empty string, S.
Perform Q operations of the following 4 types:
- append (W) - Append string W to the end of S.
- delete(K) - Delete the last k characters of S.
- print(k) - Print the k**th character of S.
- 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
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;
}
#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;
}
#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();
}
}
#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);
});
#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()