Process String with Special Operations I solution and explanation
Google
9 more videos on this problem
Process String with Special Operations I | Simple Simulation | Leetcode 3612 | codestorywithMIKcodestorywithMIK · 7:54 · 2K views
3612. Process String with Special Operations I | Leetcode Daily - PythonLeetcode Daily · 4:43 · 279 views
Daily Leetcode #2268: Jun 16, 2026 - 3612. Process String with Special Operations IProgramming Live with Larry · 3:42 · 224 views
Process String with Special Operations I | LeetCode 3612 - Pythonimpoldev · 4:12 · 144 views
Process String with Special Operations I 🔥 Leetcode 3612 | Interview Friendly Solution Study Placement · 14:15 · 126 views
LeetCode 3612: Process String with Special Operations I | String Simulation | Java C++ PythonDCode Thought · 6:59 · 76 views
LeetCode 3612: Process String with Special Operations I | Java Solution | String ManipulationCode Scribbler · 4:05 · 73 views
LeetCode 3612 | Process String with Special Operations I | Java Solution | Easy String ProblemHEMANT_CODES · 6:07 · 64 views
LeetCode 3612 Solved in Tamil | Process String with Special Operations I | String Trick | Ask AdiAsk Adi · 11:41 · 48 views
3612. Process String with Special Operations I | Leetcode Weekly Contest 458 | String, List, ArrayBreak and Build · 9:05 · 46 views
The problem
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 fromresult, if it exists. - A
'#'duplicates the currentresultand appends it to itself. - A
'%'reverses the currentresult.
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 <= 20sconsists 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 inresult(if it exists). - If the character is
#, copyresultand append it to itself. - If the character is
%, reverseresult.
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).
class Solution:
def processStr(self, s: str) -> str:
result = []
for c in s:
if c.isalpha():
result.append(c)
elif c == "*" and result:
result.pop()
elif c == "#":
result.extend(result)
elif c == "%":
result.reverse()
return "".join(result)class Solution {
public String processStr(String s) {
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetter(c)) {
result.append(c);
} else if (c == '*') {
result.setLength(Math.max(0, result.length() - 1));
} else if (c == '#') {
result.append(result);
} else if (c == '%') {
result.reverse();
}
}
return result.toString();
}
}class Solution {
public:
string processStr(string s) {
string result;
for (char c : s) {
if (isalpha(c)) {
result += c;
} else if (c == '*') {
if (!result.empty()) {
result.pop_back();
}
} else if (c == '#') {
result += result;
} else if (c == '%') {
ranges::reverse(result);
}
}
return result;
}
};function processStr(s: string): string {
const result: string[] = [];
for (const c of s) {
if (/[a-zA-Z]/.test(c)) {
result.push(c);
} else if (c === '*') {
if (result.length > 0) {
result.pop();
}
} else if (c === '#') {
result.push(...result);
} else if (c === '%') {
result.reverse();
}
}
return result.join('');
}func processStr(s string) string {
var result []rune
for _, c := range s {
if unicode.IsLetter(c) {
result = append(result, c)
} else if c == '*' {
if len(result) > 0 {
result = result[:len(result)-1]
}
} else if c == '#' {
result = append(result, result...)
} else if c == '%' {
slices.Reverse(result)
}
}
return string(result)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive String Simulation | O(n²) | O(n) | Simple implementation when constraints are small or when first reasoning about the problem |
| Stack / String Builder Simulation | O(n) | O(n) | Best general solution; processes the string in one pass without rebuilding intermediate results |
| Deque with Reverse Flag | O(n) | O(n) | Useful when operations frequently reverse the string; avoids expensive full reversals |
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.