3614. Process String with Special Operations II

HardStringSimulation

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a string s made up of lowercase English letters along with three special characters: '*', '#', and '%'. You are also given an integer k.

Your task is to build a new string called result by reading through s one character at a time, from left to right, and applying the following rules:

If the current character is a lowercase English letter, append it to the end of result.
If the current character is a '*', remove the last character from result (if result is currently empty, nothing happens).
If the current character is a '#', duplicate the current result and append that copy to itself. For example, if result is "ab", it becomes "abab".
If the current character is a '%', reverse the current result. For example, if result is "abc", it becomes "cba".

After processing every character in s, you obtain the final result string.

Return the character located at index k (0-indexed) of this final result string. If k is out of bounds (that is, k is greater than or equal to the length of result), return the character '.' instead.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

The problem simulates string operations (append, delete, duplicate, reverse) using backward tracing from index k to avoid exponential memory growth.

Open in Flowchart

Intuition

The most direct idea is to actually build the result string by simulating every operation. However, the '#' operation doubles the length of result each time it appears. If the string s contains many '#' characters, the final result could grow exponentially large — far too big to store in memory or build in practice.

The key observation is that we don't need the entire result string. We only need to know a single character: the one at index k. This suggests that instead of building the string forward, we can work backwards and trace where that single position k came from at each step.

To do this, we first compute only the length m of the final result, without storing the actual characters. We scan s from left to right and track how the length changes:

A letter increases the length by 1.
A '*' decreases the length by 1 (but never below 0).
A '#' doubles the length (m <<= 1).
A '%' leaves the length unchanged, since reversing doesn't add or remove characters.

Once we know m, we can immediately check if k >= m. If so, k is out of bounds and the answer is '.'.

Otherwise, we walk through s in reverse, undoing each operation while keeping track of where index k would map to in the smaller, earlier version of result:

Reversing a '*': the string was longer before the removal, so we increase m by 1. The index k is unaffected.
Reversing a '#': before duplication, the string was half as long. We set m //= 2. If k currently points into the second half (k >= m), it really originated from the first half, so we subtract m from k to map it back.
Reversing a '%': since the string was reversed, the character at index k was originally at index m - 1 - k, so we update k accordingly.
Reversing a letter: this letter occupied the last position of result at that moment. We decrease m by 1, and if k == m, then this very letter is the character we're looking for — so we return it.

By following the position k backward through every operation, we pinpoint the exact letter that ends up at index k without ever constructing the huge result string. This turns a potentially exponential problem into one that runs in linear time relative to the length of s.

Solution Approach

Solution 1: Reverse Tracking

We first calculate the length m of the processed result string result. If k >= m, it indicates that k exceeds the valid indices of the result string, so we return '.'.

To compute m, we scan s from left to right and simulate only the length changes:

If the character is '*', we set m = max(0, m - 1) to ensure the length never goes below 0.
If the character is '#', we double the length with m <<= 1.
If the character is a letter (i.e., not '%'), we increase m by 1.
If the character is '%', the length stays the same, so we do nothing.

After this pass, m holds the exact length of the final result. We check if k >= m: return ".".

Otherwise, we traverse the string s in reverse order and handle each character based on the following cases, updating m and k as we undo each operation:

If s[i] is '*', we increase m by 1. This restores the character that was removed, but the position k we are tracking is not affected.
If s[i] is '#', we divide m by 2 with m //= 2. At this point, if k >= m, it means k was pointing into the duplicated second half, so we map it back to the first half by subtracting: k -= m.
If s[i] is '%', the string was reversed at this step, so the character now at index k originally sat at index m - 1 - k. We update k = m - 1 - k.
Otherwise, s[i] is a letter. We decrease m by 1, since this letter occupied the last slot of result at this moment. If k == m, we have located the k-th character, so we return s[i].

By tracing the position k backward through every operation, we identify the original letter without building the enormous result string.

Complexity Analysis:

Time complexity: O(n), where n is the length of s. We make one forward pass to compute the length and one reverse pass to locate the character.
Space complexity: O(1). We only use a few integer variables (m and k) and never construct the actual result string.

Example Walkthrough

Let's trace through a small example to see how reverse tracking works.

Input: s = "ab#%*", k = 2

First, let's understand what the forward simulation would produce (for verification only):

Step	Char	Operation	`result`
1	`'a'`	append `'a'`	`"a"`
2	`'b'`	append `'b'`	`"ab"`
3	`'#'`	duplicate	`"abab"`
4	`'%'`	reverse	`"baba"`
5	`'*'`	remove last	`"bab"`

So the final result is "bab", and the character at index k = 2 is 'b'. Now let's confirm the algorithm reaches the same answer without building this string.

Phase 1: Compute the length `m` (forward pass)

We scan s left to right, tracking only the length:

Char	Rule	`m`
start	—	`0`
`'a'`	letter, `m + 1`	`1`
`'b'`	letter, `m + 1`	`2`
`'#'`	double, `m << 1`	`4`
`'%'`	reverse, unchanged	`4`
`'*'`	remove, `max(0, m - 1)`	`3`

Final length m = 3. Since k = 2 and 2 < 3, k is in bounds, so we proceed.

Phase 2: Trace `k` backward (reverse pass)

We now walk s from right to left, undoing each operation. We start with m = 3 and k = 2.

Step 1 — s[4] = '*' (undo a removal) The string was longer before the removal, so restore: m = m + 1 = 4. The tracked index k is unaffected → k = 2.

Step 2 — s[3] = '%' (undo a reverse) Before reversal, index k sat at position m - 1 - k: k = 4 - 1 - 2 = 1. m stays 4 → k = 1.

Step 3 — s[2] = '#' (undo a duplication) Before duplication the string was half as long: m = m // 2 = 2. Is k >= m? 1 >= 2 is false, so k was already in the first half — no change. → k = 1.

Step 4 — s[1] = 'b' (undo a letter append) This letter occupied the last slot, so m = m - 1 = 1. Is k == m? 1 == 1 is true → this letter is our answer.

Return 'b'. ✅

Why this matches

The forward simulation gave us "bab" with 'b' at index 2, and the backward trace pinpointed the exact same 'b' (the letter 'b' from s[1]) — all while never constructing a string larger than a few integer variables. This is the core benefit: even if '#' had appeared many times and blown result up to an enormous size, we still follow just one position back to its origin in O(n) time.

Solution Implementation

1class Solution:
2    def processStr(self, s: str, k: int) -> str:
3        # Phase 1: compute the final length of the transformed string.
4        length = 0
5        for ch in s:
6            if ch == "*":
7                # Remove the last character; length cannot go below 0.
8                length = max(0, length - 1)
9            elif ch == "#":
10                # Duplicate the entire string; length doubles.
11                length <<= 1
12            elif ch != "%":
13                # A normal character is appended; length grows by 1.
14                # '%' (reverse) leaves the length unchanged, so it's skipped here.
15                length += 1
16
17        # If k is beyond the final length, the index is invalid.
18        if k >= length:
19            return "."
20
21        # Phase 2: walk the operations in reverse, mapping index k back
22        # through each transformation to find the originating character.
23        for ch in reversed(s):
24            if ch == "*":
25                # Undo a removal: the string was one character longer before.
26                length += 1
27            elif ch == "#":
28                # Undo a duplication: the original half had length // 2.
29                length //= 2
30                # If k fell in the duplicated (second) half, shift it back
31                # into the corresponding index of the first half.
32                if k >= length:
33                    k -= length
34            elif ch == "%":
35                # Undo a reversal: index k maps to its mirrored position.
36                k = length - 1 - k
37            else:
38                # Undo an append: this character occupied the last slot.
39                length -= 1
40                # If k points exactly to that last slot, it's the answer.
41                if k == length:
42                    return ch
43

1class Solution {
2    /**
3     * Finds the character at index k in the conceptual string produced by
4     * processing s, without building the (potentially huge) string.
5     *
6     * Operations while reading s left-to-right:
7     *   '*' : remove the last character          -> length - 1 (floored at 0)
8     *   '#' : duplicate the entire string         -> length * 2
9     *   '%' : reverse the entire string           -> length unchanged
10     *   other char : append that character        -> length + 1
11     *
12     * @param s the instruction/content string
13     * @param k the target index in the final string
14     * @return the character at index k, or '.' if k is out of bounds
15     */
16    public char processStr(String s, long k) {
17        long length = 0;
18
19        // First pass: compute the total length of the final string.
20        for (int i = 0; i < s.length(); i++) {
21            char c = s.charAt(i);
22            if (c == '*') {
23                // Removing a character cannot make the length negative.
24                length = Math.max(0, length - 1);
25            } else if (c == '#') {
26                // Duplication doubles the length.
27                length <<= 1;
28            } else if (c != '%') {
29                // Any normal (non-reverse) character appends one unit.
30                length += 1;
31            }
32            // '%' (reverse) leaves the length unchanged.
33        }
34
35        // If k lies outside the final string, there is no such character.
36        if (k >= length) {
37            return '.';
38        }
39
40        // Second pass: walk backwards, undoing each operation and mapping
41        // the target index k back to the state before that operation.
42        for (int i = s.length() - 1; ; i--) {
43            char c = s.charAt(i);
44            if (c == '*') {
45                // Undo a deletion: the string was one character longer before.
46                length += 1;
47            } else if (c == '#') {
48                // Undo a duplication: the original half had length / 2.
49                length /= 2;
50                // If k pointed into the duplicated (second) half,
51                // shift it back into the original (first) half.
52                if (k >= length) {
53                    k -= length;
54                }
55            } else if (c == '%') {
56                // Undo a reversal: index k maps to its mirrored position.
57                k = length - 1 - k;
58            } else {
59                // Undo an append: this normal char occupied the last slot.
60                length -= 1;
61                // If k points to that last slot, this is the answer.
62                if (k == length) {
63                    return c;
64                }
65            }
66        }
67    }
68}
69

1class Solution {
2public:
3    char processStr(string s, long long k) {
4        // Phase 1: compute the final virtual string length by simulating
5        // each operation, tracking only the length (not the actual content).
6        long long length = 0;
7        for (char c : s) {
8            if (c == '*') {
9                // Remove last character; clamp length at 0.
10                length = max(0LL, length - 1);
11            } else if (c == '#') {
12                // Duplicate the string, doubling its length.
13                length <<= 1;
14            } else if (c != '%') {
15                // Regular character (not reverse): append, length grows by 1.
16                length += 1;
17            }
18            // '%' reverses the string; length is unchanged, so skip it here.
19        }
20
21        // If k is out of bounds for the final string, return placeholder.
22        if (k >= length) {
23            return '.';
24        }
25
26        // Phase 2: walk the operations in reverse, mapping index k back
27        // through each transformation until it pinpoints an original character.
28        for (int i = s.length() - 1;; i--) {
29            char c = s[i];
30            if (c == '*') {
31                // Undo a removal: the length had been reduced by 1,
32                // so restore it. Index k is unaffected.
33                length += 1;
34            } else if (c == '#') {
35                // Undo a duplication: halve the length back to one copy.
36                length /= 2;
37                // If k pointed into the second copy, remap it onto the first.
38                if (k >= length) {
39                    k -= length;
40                }
41            } else if (c == '%') {
42                // Undo a reversal: mirror the index across the string.
43                k = length - 1 - k;
44            } else {
45                // Undo appending a regular character: length shrinks by 1.
46                length -= 1;
47                // If k lands exactly on this character's position, it's the answer.
48                if (k == length) {
49                    return c;
50                }
51            }
52        }
53    }
54};
55

1/**
2 * Determines the character located at index k in the conceptually
3 * processed string, without actually building the (possibly enormous) string.
4 *
5 * Operations encoded in s:
6 *   '*' -> remove the last character (length decreases by 1, floored at 0)
7 *   '#' -> duplicate the current string (length doubles)
8 *   '%' -> reverse the current string (length unchanged)
9 *   any other char -> append that character (length increases by 1)
10 *
11 * @param s - the operation/character sequence
12 * @param k - the target index (0-based) into the final string
13 * @returns the character at index k, or '.' if k is out of bounds
14 */
15function processStr(s: string, k: number): string {
16    // length tracks the conceptual string length using BigInt to avoid overflow
17    let length = 0n;
18
19    // Forward pass: compute the final length of the processed string.
20    for (let i = 0; i < s.length; i++) {
21        const char = s[i];
22        if (char === '*') {
23            // Remove last character; length cannot go below 0.
24            const reduced = length - 1n;
25            length = reduced > 0n ? reduced : 0n;
26        } else if (char === '#') {
27            // Duplicate the string: length doubles.
28            length <<= 1n;
29        } else if (char !== '%') {
30            // Append a regular character.
31            length += 1n;
32        }
33        // '%' (reverse) leaves the length unchanged.
34    }
35
36    // If the requested index is outside the final string, return placeholder.
37    if (BigInt(k) >= length) {
38        return '.';
39    }
40
41    // Backward pass: walk the operations in reverse, undoing each one and
42    // remapping targetIndex so it always refers to the current intermediate string.
43    let targetIndex = BigInt(k);
44    for (let i = s.length - 1; ; i--) {
45        const char = s[i];
46        if (char === '*') {
47            // Undo a removal: the string was longer before this op.
48            length += 1n;
49        } else if (char === '#') {
50            // Undo a duplication: the original was half the current length.
51            length /= 2n;
52            // If targetIndex falls in the duplicated (second) half,
53            // map it back into the first half.
54            if (targetIndex >= length) {
55                targetIndex -= length;
56            }
57        } else if (char === '%') {
58            // Undo a reverse: mirror the index within the current length.
59            targetIndex = length - 1n - targetIndex;
60        } else {
61            // Undo an append: this letter occupied the last position.
62            length -= 1n;
63            // If targetIndex points exactly to this character, it's the answer.
64            if (targetIndex === length) {
65                return char;
66            }
67        }
68    }
69}
70

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two sequential passes over the string s, where n is the length of s:

First pass (forward): The loop iterates through each character c in s to compute the final length m. For each character, only constant-time operations are performed (comparisons, addition, subtraction, bit shift m <<= 1). This pass takes O(n) time.
Second pass (reverse): The loop iterates through each character in reversed(s), again performing only constant-time operations (comparisons, addition, subtraction, integer division m //= 2, and the assignment k = m - 1 - k). This pass also takes O(n) time.

Since the two passes are sequential, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space, regardless of the input size:

The variable m stores an integer count.
The variable k stores the index being tracked.
The loop variable c holds a single character at a time.

Note that reversed(s) returns an iterator rather than creating a new copy of the string, so it does not consume additional O(n) space. Therefore, the auxiliary space complexity is O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to clamp the length at `0` when processing `'*'`

A very common mistake is to write length -= 1 instead of length = max(0, length - 1) when handling the '*' operation in Phase 1.

The problem explicitly states that if result is empty, a '*' does nothing. If you blindly decrement, the length can become negative, which then corrupts every later computation. For example, with s = "*#a":

Correct: * → length = max(0, 0 - 1) = 0; # → 0 << 1 = 0; a → 1. Final length 1.
Wrong: * → length = -1; # → -1 << 1 = -2; a → -1. The length is garbage, and the k >= length check breaks entirely.

Solution: Always clamp the length when undoing a deletion in the forward pass:

if ch == "*":
    length = max(0, length - 1)   # never let length drop below 0

Pitfall 2: Mishandling the `'#'` (duplicate) mapping in reverse

When undoing a '#', the order of operations matters. You must first halve the length, and then compare k against the new (halved) length to decide whether k landed in the duplicated second half.

elif ch == "#":
    length //= 2          # halve FIRST
    if k >= length:       # THEN test against the new length
        k -= length

A frequent error is testing k against the old (full) length, or subtracting before halving. Both produce an incorrect mapping. Remember: after duplication the string is first + first. An index k in [length, 2*length) corresponds to position k - length in the original half, so the subtraction must use the halved length.

Pitfall 3: Off-by-one in the reverse (`'%'`) mapping

When undoing a reversal, the mirrored index is length - 1 - k, not length - k:

elif ch == "%":
    k = length - 1 - k

Because indices are 0-based, the first element (index 0) and the last element (index length - 1) swap places. Using length - k shifts everything by one and silently returns the wrong character (or even an out-of-range index). Note also that length here is the current length at this step — since '%' does not change the length, no length update is needed, but the mapping must use the length that is correct at that moment in the reverse walk.

Pitfall 4: Building the actual `result` string

The most tempting but fatal approach is to literally simulate the operations and construct result, then index into it:

# DON'T DO THIS
result = []
for ch in s:
    if ch == "#":
        result = result + result   # length doubles every '#'
    ...
return result[k]

Each '#' doubles the string, so with just 60 '#' characters the string would exceed 2^60 characters — far beyond available memory, causing a MemoryError or timeout.

Solution: Never materialize result. Track only the integer length and map the index k backward through the operations, as the reverse-tracking approach does. This keeps the solution at O(n) time and O(1) extra space regardless of how large the conceptual result grows.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know