Algorithm


Problem Name: Data Structures - Simple Text Editor

Problem Link: https://www.hackerrank.com/challenges/simple-text-editor/problem?isFullScreen=true

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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor

#5 Code Example with PHP Programming

Code - PHP Programming



Copy The Code & Try With Live Editor

#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 & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Largest Rectangle solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Waiter solution in Hackerrank - Hacerrank solution C, C++, java,js, Python, C#