TopCoder problem "Undo" used in SRM 419 (Division I Level One , Division II Level Two)

Problem Statement


You are writing a simple text editor that supports only the following two commands:

  • "type c" where c is a character: Append character c to the end of the current text.
  • "undo t" where t is an integer: Undo all operations that were performed in the previous t seconds in reverse order.

All quotes are for clarity only. The text in the editor is initially empty.

For example, consider the following sequence of commands:

Second 1: type a
Second 2: type b
Second 3: type c
Second 5: undo 3

At the end of second 3, the text is "abc". At second 5, all commands performed in the previous 3 seconds are undone in reverse order. This means 'c' is removed, and then 'b' is removed. The text becomes just "a".

Note that "undo" commands can also be undone. For example:

Second 1: type a
Second 2: type b
Second 3: undo 2
Second 4: undo 2

After second 2, the text is "ab". After second 3, everything is undone, and the text becomes empty. At second 4, the previous "undo" is undone, so the text becomes "ab" again. Then, the "type b" is also undone and the text becomes just "a".

You are given a String[] commands and a int[] time. Each element of commands is a single command, and commands[i] is performed at time[i]. The commands are given in chronological order. Return the text after all the commands are executed.



Parameters:String[], int[]
Method signature:String getText(String[] commands, int[] time)
(be sure your method is public)


-commands will contain between 1 and 50 elements, inclusive.
-Each element of commands will be either "type c" where c is a lowercase letter ('a'-'z') or "undo t" where t is an integer between 1 and 10^9, inclusive, with no leading zeroes (quotes for clarity only).
-time will contain the same number of elements as commands.
-Each element of time will be between 1 and 10^9, inclusive.
-The elements of time will be in strictly ascending order.


{"type a", "type b", "type c", "undo 3"}
{1, 2, 3, 5}
Returns: "a"
The first example from the problem statement.
{"type a", "type b", "undo 2", "undo 2"}
Returns: "a"
The second example from the problem statement.
{"type a", "undo 1", "undo 1"}
Returns: "a"
{"type a", "type b", "type c", "undo 10"}
{1, 2, 3, 1000}
Returns: "abc"
Note that "undo" can undo nothing if it is too late.
{"undo 1"}
Returns: ""

Problem url:

Problem stats url:




PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Simulation, String Manipulation, String Parsing