Skip to main content
Talentd

Process String with Special Operations I - Solution & Explanation

MediumStringSimulation8 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

You are given a string s consisting of lowercase English letters and the special characters: *, #, and %.

Build a new string result by processing s according to the following rules from left to right:

  • If the letter is a lowercase English letter append it to result.
  • A '*' removes the last character from result, if it exists.
  • A '#' duplicates the current result and appends it to itself.
  • A '%' reverses the current result.

Return the final string result after processing all characters in s.

 

Example 1:

Input: s = "a#b%*"

Output: "ba"

Explanation:

i s[i] Operation Current result
0 'a' Append 'a' "a"
1 '#' Duplicate result "aa"
2 'b' Append 'b' "aab"
3 '%' Reverse result "baa"
4 '*' Remove the last character "ba"

Thus, the final result is "ba".

Example 2:

Input: s = "z*#"

Output: ""

Explanation:

i s[i] Operation Current result
0 'z' Append 'z' "z"
1 '*' Remove the last character ""
2 '#' Duplicate the string ""

Thus, the final result is "".

 

Constraints:

  • 1 <= s.length <= 20
  • s consists of only lowercase English letters and special characters *, #, and %.

Approach Overview

Problem Overview: You receive a string that contains normal characters mixed with special operation characters. Each operation modifies the current result string (for example deleting, reversing, or altering previously processed characters). The task is to process the string from left to right and return the final string after applying every operation.

Approach 1: Naive String Simulation (O(n²) time, O(n) space)

The most direct approach is to simulate the process using a mutable string and apply operations immediately as they appear. Iterate through the input and append regular characters to the result string. When a special operation appears, modify the string accordingly (for example removing the last character or reversing the entire string). Operations like full reversal or repeated string concatenation can cost O(n) each, which pushes the worst‑case complexity to O(n²). This approach is simple and mirrors the problem statement, but it becomes slow when the string grows large.

Approach 2: Optimized Simulation with Stack / String Builder (O(n) time, O(n) space)

A more efficient strategy uses a dynamic container such as a stack, list, or StringBuilder. Iterate through the input exactly once. Regular characters are appended to the container. When an operation appears, apply the corresponding modification directly to the container (for example pop for deletion operations or toggling a flag for operations like reversal). By avoiding repeated full-string rebuilds, every character is processed at most once, giving O(n) time complexity and O(n) auxiliary space.

Many implementations also use a boolean flag to represent logical reversal instead of physically reversing the string each time. Characters are appended to either the front or back depending on the flag, typically using a deque. This technique keeps each operation constant time while preserving the correct order of characters.

This problem is primarily a simulation exercise combined with careful string manipulation from the string category. The key idea is to represent the evolving result efficiently and apply operations without repeatedly rebuilding the entire string.

Recommended for interviews: The optimized simulation using a stack, deque, or string builder. Interviewers expect you to process the string in one pass and avoid expensive operations like repeated reversal or concatenation. Showing the naive simulation demonstrates understanding, but the O(n) implementation proves you can reason about performance and data structure choices.

Solution

We can directly simulate the operations described in the problem. We use a list result to store the current result string. For each character in the input string s, we perform the corresponding operation based on the character type:

  • If the character is a lowercase English letter, add it to result.
  • If the character is *, delete the last character in result (if it exists).
  • If the character is #, copy result and append it to itself.
  • If the character is %, reverse result.

Finally, we convert result to a string and return it.

The time complexity is O(2^n), where n is the length of string s. In the worst case, the # operation may cause the length of result to double each time, resulting in exponential time complexity. Ignoring the space consumption of the answer, the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive String SimulationO(n²)O(n)Simple implementation when constraints are small or when first reasoning about the problem
Stack / String Builder SimulationO(n)O(n)Best general solution; processes the string in one pass without rebuilding intermediate results
Deque with Reverse FlagO(n)O(n)Useful when operations frequently reverse the string; avoids expensive full reversals

Video Solution

Process String with Special Operations I | Simple Simulation | Leetcode 3612 | codestorywithMIK • codestorywithMIK • 2,993 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Process String with Special Operations I easy or hard?
Process String with Special Operations I is generally rated Medium difficulty. The logic itself is straightforward, but the challenge comes from efficiently simulating operations without repeatedly rebuilding the string.
Process String with Special Operations I Python/Java solution
In Python the solution typically uses a list or deque to append characters and pop when an operation requires removal. Java implementations commonly use StringBuilder or ArrayDeque. The same O(n) simulation logic applies in C++, Go, and TypeScript.
How to solve Process String with Special Operations I in O(n)?
Traverse the string from left to right and maintain a dynamic container such as a stack or deque. Append normal characters and directly apply operations (such as deletion or logical reversal) on the container. Avoid rebuilding or reversing the full string repeatedly so every step remains O(1).
What is the best approach for Process String with Special Operations I?
The most efficient approach is a one-pass simulation using a stack, deque, or string builder. Iterate through the input string and update the result structure whenever a special operation appears. Each character is processed once, giving O(n) time and O(n) space complexity.
Is Process String with Special Operations I asked at Google/Amazon/Meta?
String simulation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variations often involve processing command characters, implementing undo-like behavior, or simulating editors with stack-based logic.
What data structure is used in Process String with Special Operations I?
Typical solutions use a stack, dynamic array, deque, or language-specific structure like StringBuilder. These structures support efficient append, pop, and sometimes front insertion operations needed to simulate the string transformations.
What is the time complexity of Process String with Special Operations I?
The optimal solution runs in O(n) time because the string is processed exactly once and each operation modifies the result in constant time. Space complexity is O(n) since the resulting processed string may store up to n characters.

Ready to solve this problem?

Practice Process String with Special Operations I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring