LeetCode 3614 - Process String with Special Operations II

Difficulty: 🔴 Hard
Topics: String, Simulation

Solution

Problem Understanding

The problem defines a transformation process over a string s that contains lowercase letters and three special operation characters: '*', '#', and '%'. We process the string from left to right, maintaining a dynamically changing result string.

Each lowercase letter is appended to the result. The '*' operation deletes the last character of the result if it exists. The '#' operation duplicates the current result and appends it to itself, effectively doubling its length. The '%' operation reverses the entire current result string.

After processing all characters, we are asked to return the character at index k (0-based) of the final result string. If k is outside the bounds of the final string, we return '.'.

The constraints make it clear that the final string can grow extremely large, up to 10^15 in length, which makes it impossible to construct explicitly. The string s itself can be up to 10^5 characters, so we must work in linear time relative to s, not the final result size.

The key edge cases include scenarios where deletions happen on an empty string, repeated duplications causing exponential growth, reversals interleaved with duplications, and queries where k exceeds the final length. Another subtle case is when the result becomes empty and later operations depend on that empty state.

Approaches

The brute-force approach directly simulates the string transformation using an actual mutable string structure such as a list of characters. Each operation is applied literally: appending characters, popping for '*', concatenating for '#', and reversing for '%'. While conceptually straightforward, this approach fails because '#' can double the string repeatedly, leading to exponential growth and memory overflow.

The optimal approach avoids constructing the string entirely. Instead, it tracks only the length of the string after each operation and then reconstructs the answer backwards. The key insight is that every operation is invertible in terms of index mapping: we do not need the full string, only where the k-th character would originate from in earlier states. By maintaining prefix lengths and then walking the operations in reverse, we can "trace back" the origin of the character at index k.

This reverse simulation transforms exponential string growth into a linear-time index mapping problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n) in worst case	O(2^n)	Direct simulation with actual string operations
Optimal	O(n)	O(n)	Track lengths and reverse-map index instead of building string

Algorithm Walkthrough

The optimal solution relies on two passes over the input string.

We first simulate the operations from left to right, but instead of building the string, we maintain an array length[i] representing the length of the result after processing s[i]. This allows us to know the final size and intermediate sizes without storing the string itself.
Once we know the final length, we check if k is outside [0, length[n]-1]. If it is, we immediately return '.' because the index is invalid.
We then iterate backward from the last character of s to the first, maintaining a variable cur_len representing the current effective length of the string segment we are considering and a variable k representing the index we are trying to locate within that segment.
When we encounter a lowercase letter, we know it contributed exactly one character to the string. If k equals cur_len - 1, that letter is the answer. Otherwise, we reduce cur_len by 1 and continue backward.
When we encounter '*', we reverse the deletion operation. Since forward execution removed the last character (if any), backward execution simply restores the previous length using length[i-1]. The index k remains unchanged.
When we encounter '#', we reverse the duplication. If k is greater than or equal to half of the current length, it must have come from the second half, so we subtract half the length from k. Then we update cur_len to half.
When we encounter '%', we reverse the reversal. This means we remap the index using k = cur_len - 1 - k. The length remains unchanged.
We continue this process until we find the originating character.

Why it works

The correctness comes from the fact that every operation defines a deterministic transformation of indices. By storing only lengths and applying inverse transformations, we effectively trace the origin of any character in a functional transformation system. This ensures that each step preserves correctness of index mapping without needing to construct intermediate strings. The problem asks us to simulate the transformation of a string s containing lowercase letters and special characters '*', '#', and '%' to build a new string result. We process the string from left to right, applying these operations in order. Each letter is appended to the result. The '*' removes the last character if one exists, '#' duplicates the current result, and '%' reverses the result. After processing the entire string, we need to return the character at the k-th index of result or '.' if k is out of bounds.

The input s has a length up to 10^5, but the resulting string can grow up to 10^15 because of repeated duplication. Directly constructing the result is infeasible for large cases due to memory and time limits. The k value can also be extremely large (up to 10^15), which emphasizes the need for an approach that avoids building the entire string.

Important edge cases include strings that immediately remove characters with '*', strings that duplicate an empty string with '#', or strings that reverse multiple times. We must also correctly handle k values that exceed the final string length.

Approaches

The brute-force approach is straightforward. We iterate through the string s and maintain a mutable result list. For each character, we perform the operation: append letters, remove the last character for '*', duplicate for '#', and reverse for '%'. After processing, we return result[k] if it exists. This approach is correct because it simulates the rules directly. However, it is too slow and memory-intensive for the given constraints, especially when '#' duplicates can cause exponential growth.

The optimal approach uses recursion or simulation without constructing the entire string. The key observation is that we only need the k-th character. Instead of building result, we track the effective length after each operation and use backward reasoning. For duplication, we can determine which half of the string the k-th character falls into. For reversal, we map k to the mirrored index. For deletion, we simply reduce the length. This lets us compute the answer using length bookkeeping rather than constructing large strings.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N * M)	O(M)	N = length of s, M = length of result, impractical for large duplications
Optimal	O(N * log(result_length))	O(N)	Tracks length only, simulates operations backward to find kth character

Algorithm Walkthrough

Initialize an empty list operations to store characters and track the length after each operation.
Traverse the string s and update the length of result after each operation. Append letters, increase length for letters, double length for '#', reverse has no effect on length, decrease length by 1 for '*'.
If at any point length exceeds k + 1, note that the k-th character can potentially be found here.
Process backward from the last operation. If the current operation is '#' and k >= prev_length, map k to k - prev_length to find the corresponding character in the first half. If it is '%', map k to length - 1 - k. If it is '*', increment k if it was removed. Continue until a letter is reached.
Once a letter is reached, return it. If we backtrack past the beginning, return '.' indicating k is out of bounds.

Why it works: At each step, we maintain a mapping from k to the pre-operation index. This ensures we never build the large string but can identify the character at k correctly.

Python Solution

from typing import List

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

        for i in range(n):
            c = s[i]
            prev = length[i]

            if 'a' <= c <= 'z':
                length[i + 1] = prev + 1
            elif c == '*':
                length[i + 1] = max(0, prev - 1)
            elif c == '#':
                length[i + 1] = prev * 2
            else:  # '%'
                length[i + 1] = prev

        if k >= length[n]:
            return '.'

        cur_len = length[n]

        for i in range(n - 1, -1, -1):
            c = s[i]
            prev_len = length[i]

            if c == '%':
                k = cur_len - 1 - k

            elif c == '#':
                if k >= prev_len:
                    k -= prev_len
                cur_len = prev_len

            elif c == '*':
                cur_len = prev_len

            else:  # letter
                if k == cur_len - 1:
                    return c
                cur_len -= 1

        return '.'

The implementation first computes the length evolution across the string, ensuring we never build the actual result. It then walks backward, applying inverse operations to progressively locate the origin of the k-th character. Each branch corresponds directly to reversing one of the four operations. class Solution: def processStr(self, s: str, k: int) -> str: ops = [] length = 0 for ch in s: if ch.isalpha(): ops.append((ch, length)) length += 1 elif ch == '': if length > 0: length -= 1 ops.append(('', length)) elif ch == '#': ops.append(('#', length)) length *= 2 elif ch == '%': ops.append(('%', length))

    if k >= length:
        return '.'

    for i in range(len(ops) - 1, -1, -1):
        op, l = ops[i]
        if op.isalpha():
            if k == l:
                return op
        elif op == '*':
            if k == l:
                # kth character was removed
                return '.'
            elif k > l:
                k += 1
        elif op == '#':
            if k >= l:
                k %= l
        elif op == '%':
            k = l - 1 - k
    return '.'


The Python implementation first computes the length of `result` after each operation, storing it alongside the operation in `ops`. The backward traversal efficiently finds the `k`-th character by adjusting `k` according to the inverse of each operation.

## Go Solution

```go
func processStr(s string, k int64) byte {
	n := len(s)
	length := make([]int64, n+1)

	for i := 0; i < n; i++ {
		prev := length[i]
		c := s[i]

		if c >= 'a' && c <= 'z' {
			length[i+1] = prev + 1
		} else if c == '*' {
			if prev > 0 {
				length[i+1] = prev - 1
			} else {
				length[i+1] = 0
			}
		} else if c == '#' {
			length[i+1] = prev * 2
		} else {
			length[i+1] = prev
		}
	}

	if k >= length[n] {
		return '.'
	}

	curLen := length[n]

	for i := n - 1; i >= 0; i-- {
		c := s[i]
		prevLen := length[i]

		if c == '%' {
			k = curLen - 1 - k
		} else if c == '#' {
			if k >= prevLen {
				k -= prevLen
			}
			curLen = prevLen
		} else if c == '*' {
			curLen = prevLen
		} else {
			if k == curLen-1 {
				return c
			}
			curLen--
		}
	}

	return '.'
}

In Go, we explicitly use int64 for lengths and index k to avoid overflow, since the final string size can reach 10^15. The logic mirrors the Python solution, with careful handling of rune classification via byte comparison. The main difference is static typing and explicit overflow safety.

Worked Examples

Example 1: `s = "a#b%*", k = 1`

Forward length computation:

i	s[i]	Operation	Length
0	a	+1	1
1	#	double	2
2	b	+1	3
3	%	reverse	3
4	*	-1	2

Final length is 2, so k = 1 is valid.

Backward tracing:

Start: cur_len = 2, k = 1

At '*': previous length 3 → cur_len = 3

At '%': reverse → k = 3 - 1 - 1 = 1

At 'b': since k != 2, move left, cur_len = 2

At '#': previous length 1, k >= 1 so k = 0, cur_len = 1

At 'a': k == 0, return 'a'

Example 2: `s = "cd%#*", k = 3`

After full simulation, final string length is 6.

Backward traversal identifies that index 3 maps into the duplicated segment and resolves to 'd' after reversing transformations step by step.

Example 3: `s = "z*#", k = 0`

Forward result becomes empty string, so length is 0. Since k = 0 is out of bounds, we immediately return '.' without backward processing. type op struct { ch byte len int64 } ops := make([]op, 0, len(s)) var length int64 = 0 for i := 0; i < len(s); i++ { ch := s[i] switch ch { case '*': if length > 0 { length-- } ops = append(ops, op{ch, length}) case '#': ops = append(ops, op{ch, length}) length *= 2 case '%': ops = append(ops, op{ch, length}) default: ops = append(ops, op{ch, length}) length++ } }

if k >= length {
    return '.'
}

for i := len(ops) - 1; i >= 0; i-- {
    o := ops[i]
    ch, l := o.ch, o.len
    switch ch {
    case '*':
        if k == l {
            return '.'
        } else if k > l {
            k++
        }
    case '#':
        if k >= l {
            k %= l
        }
    case '%':
        k = l - 1 - k
    default:
        if k == l {
            return ch
        }
    }
}
return '.'

}


Go-specific differences include defining a struct `op` to store operations with their effective length. Go requires explicit type conversion and careful handling of `int64` to prevent overflow for large `k` values.

## Worked Examples

Example 1: s = "a#b%*"; k = 1

| i | s[i] | Operation | Length | Comment |
| --- | --- | --- | --- | --- |
| 0 | 'a' | append | 1 | 'a' |
| 1 | '#' | duplicate | 2 | 'aa' |
| 2 | 'b' | append | 3 | 'aab' |
| 3 | '%' | reverse | 3 | 'baa' |
| 4 | '*' | remove | 2 | 'ba' |

Backward simulation for k=1:

- '*' l=2, k < l -> no change
- '%' l=3, k=1 -> k=2-1=1 -> maps to mirrored position
- '#' l=2, k=1 -> k < l -> remains 1
- 'a' l=1, k != l -> continue
- 'a' l=0, k != l -> continue

Result: 'a'

Example 2: s = "cd%#*#"; k=3

Forward length computation: final length=6

Backward simulation maps k step-by-step to find 'd'.

Example 3: s = "z*#"; k=0

Final length=0, k>=length, return '.'

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | One forward pass to compute lengths and one backward pass to resolve index |
| Space | O(n) | Storage of length array for each prefix state |

The algorithm is linear because each character is processed a constant number of times, and no operation depends on the final string size. The space usage is dominated by storing prefix lengths.
| Time | O(N log(result_length)) | Each operation is processed once; backward mapping uses modulo or mirroring |
| Space | O(N) | Stores operation list with lengths |

The time complexity is logarithmic in the effective length because duplication halves the problem size when tracing backward. Space is linear in `s` length since we store the operations and their lengths.

## Test Cases

assert Solution().processStr("a#b%", 1) == "a" # provided example 1 assert Solution().processStr("cd%#", 3) == "d" # provided example 2 assert Solution().processStr("z*#", 0) == "." # provided example 3

assert Solution().processStr("a", 0) == "a" # single char assert Solution().processStr("", 0) == "." # empty after deletion assert Solution().processStr("a#", 1) == "a" # duplication assert Solution().processStr("ab%", 0) == "b" # reverse assert Solution().processStr("ab#", 2) == "a" # duplicated indexing assert Solution().processStr("abcd*", 0) == "." # repeated deletions


| Test | Why |
| --- | --- |
| `"a#b%*", 1` | Mixed operations with valid index |
| `"cd%#*", 3` | duplication + reverse interaction |
| `"z*#", 0` | empty final string |
| `"a"` | simplest case |
| `"*"` | deletion on empty |
| `"a#"` | pure duplication |
| `"ab%"` | reversal correctness |
| `"ab#"` | indexing into second half |
| `"a*b*c*d*"` | repeated deletions to empty |

## Edge Cases

One important edge case is when the string becomes empty due to repeated `'*'` operations. In this case, further deletions should not reduce the length below zero. The implementation handles this by clamping length at zero during forward simulation.

Another edge case is repeated `'#'` operations that cause exponential growth in length. Since we only store lengths using 64-bit integers, we avoid memory issues while still correctly tracking the effective size of the string.

A third edge case involves the `'%'` reversal operation interacting with duplication. Because reversal changes index positions but not length, failing to adjust `k` correctly during backward traversal would lead to incorrect character mapping. The implementation explicitly remaps `k` at each reversal step, ensuring correctness even under multiple nested transformations.
# Provided examples
assert Solution().processStr("a#b%*", 1) == "a"  # simple duplication and reversal
assert Solution().processStr("cd%#*#", 3) == "d"  # multiple operations
assert Solution().processStr("z*#", 0) == "."  # empty result

# Boundary cases
assert Solution().processStr("", 0) == "."  # empty input
assert Solution().processStr("a", 0) == "a"  # single character
assert Solution().processStr("a"*100000 + "#", 99999) == "a"  # large input, duplication

# Edge with removal
assert Solution().processStr("a*", 0) == "."  # removal of only character
assert Solution().process

LeetCode 3614 - Process String with Special Operations II

Solution

Problem Understanding

Approaches

Algorithm Walkthrough

Why it works

Approaches

Algorithm Walkthrough

Python Solution

Worked Examples

Example 1: s = "a#b%*", k = 1

Example 2: s = "cd%#*", k = 3

Example 3: s = "z*#", k = 0

Example 1: `s = "a#b%*", k = 1`

Example 2: `s = "cd%#*", k = 3`

Example 3: `s = "z*#", k = 0`