3614. Process String with Special Operations II

class Solution {
    public char processStr(String s, long k) {

        int n = s.length();
        long[] len = new long[n];

        long cur = 0;

        // Calculate final length after every operation
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);

            if (ch >= 'a' && ch <= 'z') {
                cur++;
            } else if (ch == '*') {
                if (cur > 0) cur--;
            } else if (ch == '#') {
                cur = Math.min(cur * 2, (long) 1e15 + 5);
            } else { // '%'
                // length unchanged
            }

            len[i] = cur;
        }

        if (k >= cur) {
            return '.';
        }

        // Work backwards
        for (int i = n - 1; i >= 0; i--) {

            char ch = s.charAt(i);
            long before = (i == 0) ? 0 : len[i - 1];

            if (ch >= 'a' && ch <= 'z') {

                if (k == before) {
                    return ch;
                }

            } else if (ch == '*') {

                // Removed last character.
                // Existing indices stay unchanged.

            } else if (ch == '#') {

                if (before > 0 && k >= before) {
                    k -= before;
                }

            } else { // '%'

                if (before > 0) {
                    k = before - 1 - k;
                }
            }
        }

        return '.';
    }
}

class Solution:
    def processStr(self, s: str, k: int) -> str:
        n = len(s)
        length = [0] * n
        cur = 0

        for i, ch in enumerate(s):
            if 'a' <= ch <= 'z':
                cur += 1
            elif ch == '*':
                if cur > 0:
                    cur -= 1
            elif ch == '#':
                cur = min(cur * 2, 10**15 + 5)

            length[i] = cur

        if k >= cur:
            return '.'

        for i in range(n - 1, -1, -1):
            ch = s[i]
            before = 0 if i == 0 else length[i - 1]

            if 'a' <= ch <= 'z':
                if k == before:
                    return ch
            elif ch == '#':
                if before > 0 and k >= before:
                    k -= before
            elif ch == '%':
                if before > 0:
                    k = before - 1 - k

        return '.'

class Solution {
public:
    char processStr(string s, long long k) {

        int n = s.size();
        vector<long long> len(n);

        long long cur = 0;

        for (int i = 0; i < n; i++) {

            char ch = s[i];

            if ('a' <= ch && ch <= 'z')
                cur++;
            else if (ch == '*') {
                if (cur > 0) cur--;
            }
            else if (ch == '#')
                cur = min(cur * 2, (long long)1e15 + 5);

            len[i] = cur;
        }

        if (k >= cur)
            return '.';

        for (int i = n - 1; i >= 0; i--) {

            char ch = s[i];
            long long before = (i == 0) ? 0 : len[i - 1];

            if ('a' <= ch && ch <= 'z') {

                if (k == before)
                    return ch;

            } else if (ch == '#') {

                if (before > 0 && k >= before)
                    k -= before;

            } else if (ch == '%') {

                if (before > 0)
                    k = before - 1 - k;
            }
        }

        return '.';
    }
};

var processStr = function(s, k) {

    const len = new Array(s.length);
    let cur = 0;

    for (let i = 0; i < s.length; i++) {

        const ch = s[i];

        if (ch >= 'a' && ch <= 'z')
            cur++;
        else if (ch === '*') {
            if (cur > 0) cur--;
        }
        else if (ch === '#')
            cur = Math.min(cur * 2, 1e15 + 5);

        len[i] = cur;
    }

    if (k >= cur)
        return '.';

    for (let i = s.length - 1; i >= 0; i--) {

        const ch = s[i];
        const before = i === 0 ? 0 : len[i - 1];

        if (ch >= 'a' && ch <= 'z') {

            if (k === before)
                return ch;

        } else if (ch === '#') {

            if (before > 0 && k >= before)
                k -= before;

        } else if (ch === '%') {

            if (before > 0)
                k = before - 1 - k;
        }
    }

    return '.';
};