3614. Process String with Special Operations II

Time: O(n)

Space: O(1)

Problem Overview

The processed string can grow exponentially, so building it is impossible.

Intuition

The processed string can grow exponentially, so building it is impossible. Instead, run two passes on the operation string. First pass computes only the final length m by simulating * (delete last), # (double length), and letter inserts; % does not change length. If k >= m, return ".". Second pass walks backward: undo each operator to map index k to the correct position — % mirrors k (k = m - 1 - k), # maps the second half to the first, * restores a deleted slot, and letters are returned when k equals the current length after shrinking.

Algorithm

1Forward scan: maintain length m. On letter (not %), m += 1. On *, m = max(0, m - 1). On #, m <<= 1. Ignore % for length.
2If k >= m, return '.'.
3Backward scan from the last character of s:
4On *, increment m (undo delete).
5On #, set m /= 2; if k >= m, subtract m from k (index lies in the second copy).
6On %, set k = m - 1 - k (undo reverse).
7On a letter, decrement m; if k == m, return that character.

Example Walkthrough

Input: s = "a#b%", k = 2

1.Forward: a → m=1; # → m=2; b → m=3; % → m=3 (reverse does not change length).
2.k=2 < m=3, so continue.
3.Backward at %: k = 3 - 1 - 2 = 0.
4.Backward at b: m=2, k≠2.
5.Backward at #: m=1, k < m.
6.Backward at a: m=0, k==0 → return 'a'.
7.(Forward-built string is "baa"; index 2 is 'a'.)

Output: "a"

Common Pitfalls

•Do not materialise the string — length can overflow memory.
•In the forward pass, % must not change m.
•When undoing #, subtract m from k only when k >= m (k indexes the duplicated half).
•Use long for m and k if the problem allows very large results.

3614.cs

// Approach: The final string can be enormous, so never build it explicitly.
// Pass 1 (left to right): simulate operators on the length m only.
//   Letters increase m by 1; '*' deletes the last character (m = max(0, m-1));
//   '#' duplicates the string (m <<= 1); '%' only reverses and does not change length.
// If k >= m, return '.'.
// Pass 2 (right to left): undo each operator to locate the k-th character.
//   '*' adds a character back (m++); '#' halves m and maps k from the second copy to the first (if k >= m, k -= m);
//   '%' mirrors the index (k = m - 1 - k); for a letter, shrink m and return it when k == m.
// Time: O(n) Space: O(1)
public class Solution
{
    public char ProcessStr(string s, long k)
    {
        long m = 0;
        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if (c == '*')
                m = Math.Max(0, m - 1);
            else if (c == '#')
                m <<= 1;
            else if (c != '%')
                m += 1;
        }
        if (k >= m)
            return '.';
        for (int i = s.Length - 1; ; i--)
        {
            char c = s[i];
            if (c == '*')
                m += 1;
            else if (c == '#')
            {
                m /= 2;
                if (k >= m)
                    k -= m;
            }
            else if (c == '%')
                k = m - 1 - k;
            else
            {
                m -= 1;
                if (k == m)
                    return c;
            }
        }
    }
}

Was this solution helpful?