LeetCode 3612 - Process String with Special Operations I

The problem asks us to simulate the construction of a string called result by processing an input string s from left to right. The input string contains lowercase English letters and three special operators: , , and %.

leetcodemediumstringsimulation

LeetCode Problem 3612

Difficulty: 🟡 Medium
Topics: String, Simulation

Solution

Problem Understanding

The problem asks us to simulate the construction of a string called result by processing an input string s from left to right. The input string contains lowercase English letters and three special operators: *, #, and %. Each character in the input modifies the evolving result string in a specific way.

A lowercase letter is appended directly to the end of result. The * operator removes the last character of result if it exists. The # operator duplicates the entire current result and appends the duplicate to itself, effectively doubling the string. The % operator reverses the current result.

The output is the final state of result after processing all characters in order.

The constraints are small, with 1 <= s.length <= 20, which strongly indicates that a straightforward simulation is expected to pass comfortably without needing advanced optimization techniques. However, the operations # (doubling) and % (reverse) can make naive string handling inefficient if not implemented carefully, especially if strings are repeatedly copied in immutable form.

Important edge cases include an empty result when operations like *, #, or % are applied, repeated doubling causing exponential growth in conceptual size, and multiple consecutive reversals or deletions which can reduce or negate prior work.

Approaches

The brute-force approach directly simulates the process using a mutable structure such as a list of characters. Each operation is applied as described, and the list is converted back to a string at the end. This approach is correct because it mirrors the problem statement exactly. However, if implemented with immutable strings, operations like concatenation, duplication, and reversal can repeatedly copy large strings, leading to unnecessary overhead.

The key insight is that since the constraints are extremely small, we do not need to optimize beyond a clean simulation. The optimal solution is still a direct simulation, but it uses a mutable list (or stack-like structure) to avoid repeated string copying. This ensures operations like append and pop are O(1), and reverse or duplication are only performed when necessary on manageable data sizes.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) to O(n^3) O(n) Uses string concatenation and repeated copying for operations
Optimal O(n^2) worst-case O(n) Uses list-based simulation to efficiently apply operations

Algorithm Walkthrough

The optimal algorithm simulates the string construction using a dynamic list of characters.

  1. Initialize an empty list called result. This list will act as a mutable container for characters, allowing efficient append and pop operations without creating new strings.
  2. Iterate through each character c in the input string s from left to right, ensuring that operations are applied in the exact order specified by the problem.
  3. If c is a lowercase letter, append it to the end of the result list. This corresponds directly to extending the current constructed string.
  4. If c is *, check whether result is non-empty. If it is, remove the last element using a pop operation. This simulates deleting the most recently added character.
  5. If c is #, create a snapshot of the current result and extend result by appending this snapshot to itself. This effectively doubles the current string.
  6. If c is %, reverse the result list in place. This simulates reversing the current constructed string.
  7. After processing all characters, convert the list back into a string and return it as the final answer.

Why it works

The algorithm maintains an invariant that at every step, result accurately represents the string formed after processing all characters up to the current index in s. Each operation is applied exactly as defined, preserving correctness. Because list operations preserve order and allow efficient mutation, no intermediate state is lost or incorrectly transformed, ensuring the final constructed string is exact.

Python Solution

class Solution:
    def processStr(self, s: str) -> str:
        result = []

        for c in s:
            if 'a' <= c <= 'z':
                result.append(c)
            elif c == '*':
                if result:
                    result.pop()
            elif c == '#':
                result.extend(result)
            elif c == '%':
                result.reverse()

        return ''.join(result)

Implementation Explanation

The solution uses a Python list named result to store characters incrementally. This avoids costly string concatenation.

When encountering a lowercase letter, it is appended directly. The * operation safely pops the last character if it exists. The # operation duplicates the list using extend(result), which appends a snapshot of the current list. The % operation uses Python’s built-in reverse() method to invert the list in place.

Finally, the list is joined into a string, which forms the output.

Go Solution

func processStr(s string) string {
    result := make([]byte, 0)

    for i := 0; i < len(s); i++ {
        c := s[i]

        if c >= 'a' && c <= 'z' {
            result = append(result, c)
        } else if c == '*' {
            if len(result) > 0 {
                result = result[:len(result)-1]
            }
        } else if c == '#' {
            snapshot := make([]byte, len(result))
            copy(snapshot, result)
            result = append(result, snapshot...)
        } else if c == '%' {
            for l, r := 0, len(result)-1; l < r; l, r = l+1, r-1 {
                result[l], result[r] = result[r], result[l]
            }
        }
    }

    return string(result)
}

Go-specific Notes

In Go, strings are immutable, so we explicitly use a []byte slice to allow efficient mutation. The * operation is handled via slicing, which is efficient and avoids copying. For #, we must explicitly allocate a new slice and copy the current contents before appending to avoid aliasing issues. The reverse operation is implemented manually using a two-pointer swap approach since Go does not provide a built-in reverse for slices.

Worked Examples

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

We track the state of result step by step.

Step Char Operation Result
1 a append a
2 # duplicate aa
3 b append aab
4 % reverse baa
5 * delete last ba

Final output is ba.

Example 2: s = "z*#"

Step Char Operation Result
1 z append z
2 * delete last ""
3 # duplicate empty ""

Final output is an empty string.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) worst-case Each # can duplicate the entire current string, and reverse is O(n), leading to quadratic behavior overall
Space O(n) The result list stores at most the final expanded string

The complexity is dominated by the duplication and reversal operations. Even though each step is linear in the size of result, the small constraint ensures this remains efficient.

Test Cases

assert Solution().processStr("a#b%*") == "ba"  # provided example 1
assert Solution().processStr("z*#") == ""       # provided example 2

assert Solution().processStr("") == ""          # empty input edge case
assert Solution().processStr("a") == "a"        # single character
assert Solution().processStr("*") == ""         # delete on empty
assert Solution().processStr("%%a") == "a"      # double reverse cancels out
assert Solution().processStr("ab##") == "abab"  # repeated duplication
assert Solution().processStr("abc%") == "cba"   # reverse full string
assert Solution().processStr("a*b*c*") == ""    # repeated deletions
Test Why
"a#b%*" verifies mixed operations
"z*#" verifies empty duplication behavior
"" handles no input characters
"*" ensures safe deletion on empty
"%%a" validates reverse idempotence
"ab##" stress duplication logic
"abc%" validates reversal correctness
"a_b_c*" repeated deletions leading to empty

Edge Cases

One important edge case is when the string begins with *. Since there is nothing to delete, the implementation must ensure it does not attempt to pop from an empty list. This is handled by checking whether result is non-empty before popping.

Another edge case occurs with repeated # operations. Since each # duplicates the entire current string, the size can grow rapidly. However, because the input size is at most 20, even repeated doubling remains manageable. The list-based approach ensures that copying is explicit and controlled.

A final edge case involves sequences of % operations. Multiple reversals can cancel each other out logically, but the algorithm still performs each reversal explicitly. Using in-place reversal ensures correctness without needing additional state tracking.