Practice Process String with Special Operations II
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Process s from left to right, initially with an empty result. A lowercase letter is appended. The symbol * deletes the final character if one exists, # concatenates a second copy of the current result, and % reverses it. Return the character at zero-based index k in the final result, or a period (.) if k is outside its bounds. Practice approach: Record the result length after each operation without constructing the potentially huge string. If k is valid, walk the operations backwards: undo reversal by replacing k with length-1-k, undo duplication with modulo the previous length, and account for deletion by restoring its previous length. Stop when an appended letter owns the requested index. Use wide integer arithmetic; the final result can reach 10^15 characters.
Source: Process String with Special Operations II on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
s = "a#b%*", k = 1
"a"
# Example 2
s = "cd%#*#", k = 3
"d"
# Example 3
s = "z*#", k = 0
"."
Constraints
How to solve Process String with Special Operations II
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
You never need the string, only its length after each operation; with those lengths a single index can be traced backward, because reversal, duplication, and deletion each map an output position to a definite input position.
Why brute force is not enough
Simulating literally builds a string of up to 10^15 characters, since each of up to 10^5 duplications doubles the length; impossible in time or memory.
Approach
- Make a forward pass recording the length after every operation in a 64-bit array: a letter adds 1, a deletion subtracts 1 only if the length is positive, a duplication doubles, a reversal leaves it unchanged.
- If k is at least the final length, return a period.
- Walk the operations from last to first, keeping the invariant that k is the index of the sought character within the result that existed just after the current operation.
- Undo each operation: for a reversal set k to length minus one minus k using the length at that moment; for a duplication subtract the previous length if k is at least that length; for a deletion leave k alone, since removing the last character does not move earlier ones; for a letter, if k equals the length before the append that letter is the answer, otherwise k is unchanged.
- The walk always ends at a letter, because every final index originated from an appended character.
Walkthrough of Example 2
s = "cd%#*#", k = 3 → "d"
- s is "cd%#*#" and k is 3. Lengths after each operation: 1, 2, 2, 4, 3, 6. Since 3 is below 6 the index is valid.
- Undo the final duplication: the previous length was 3 and k = 3 is not below 3, so k becomes 0.
- Undo the deletion: k stays 0. Undo the earlier duplication: the previous length was 2 and k = 0 is below 2, so k stays 0.
- Undo the reversal at length 2: k becomes 2 - 1 - 0 = 1.
- Undo the append of d: the length before it was 1, equal to k, so the answer is "d", the expected output; the full string would be dcddcd.
Time and space
Time O(n) · Space O(n). n is the length of s; one forward pass records lengths and one backward pass adjusts k, with a single array of n 64-bit lengths.
Interview pitfalls
- Deleting from an empty result: the length stays 0, so recover previous lengths from the stored array rather than assuming length plus one.
- Using 32-bit integers; lengths and k reach 10^15.
- Applying the reversal formula with the final length instead of the length at that step.
- Forgetting that an intermediate length can exceed the final one by the number of later deletions, so bounds checks must use stored values.
- Walking forward and tracking a set of positions, which quickly becomes unmanageable.
Follow-up questions interviewers ask
- How would you answer many different k values for the same s, sharing the length array?
- What if an operation inserted a copy of the result at the front instead of the back?
- Could you return a whole range of characters faster than tracing each index independently?
Related LeetCode Problems
Practice more problems similar to Process String with Special Operations II.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.