Problem Description

You are given a string s consisting of lowercase English letters and the special characters: *, #, and %.

Build a new string result by processing s according to the following rules from left to right:

• If the character is a lowercase English letter, append it to result.
• If the character is *, remove the last character from result, if it exists.
• If the character is #, duplicate the current result and append it to itself.
• If the character is %, reverse the current result.

Return the final string result after processing all characters in s.

Intuition

The problem describes a process where a string is built step by step, following specific rules for each character. Each type of character encodes a simple operation that directly changes the current result. By moving through the string one character at a time and applying the corresponding operation—append, remove last, duplicate, or reverse—we can simulate the process as described. Using a list makes adding, removing, reversing, and duplicating parts efficient and straightforward, since lists can handle these operations easily in Python. The approach feels natural: just "do what the instructions say" in order, and the answer will be ready when all instructions have been followed.

Solution Approach

The solution uses simulation to directly follow the problem's operations.

1. Start by creating an empty list called result, which will store the characters of the current result string. Lists are used for their efficient operations like append, pop, and reverse.
2. Loop through each character c in the string s:
   • If c is a lowercase English letter (c.isalpha()), append it to result using result.append(c).
   • If c is * and result is not empty, remove the last character with result.pop().
   • If c is #, duplicate the current result by extending it with itself: result.extend(result).
   • If c is %, reverse the contents of result by calling result.reverse().
3. After processing all characters, join the elements in result into a string using "".join(result) and return it.

Every operation maps clearly to a list method, which keeps the implementation straightforward and efficient. The loop processes each character exactly once, and each operation (except possibly duplication) is done in constant time, making the approach practical for typical input sizes.

Example Walkthrough

Let's illustrate the solution with a small example:

Suppose the input string is: ab*c#d%

We'll process each character one by one:

1. 'a' — It's a lowercase letter. Append it to result: result = ['a']
2. 'b' — Lowercase letter. Append: result = ['a', 'b']
3. '*' — Remove last character ('b'): result = ['a']
4. 'c' — Lowercase letter. Append: result = ['a', 'c']
5. '#' — Duplicate current result and append: result = ['a', 'c', 'a', 'c']
6. 'd' — Lowercase letter. Append: result = ['a', 'c', 'a', 'c', 'd']
7. '%' — Reverse result: result = ['d', 'c', 'a', 'c', 'a']

Join the list into a string: Final output: "dcaca"

This step-by-step simulation demonstrates how each operation modifies the state, and how directly following the set of rules yields the final processed string.

Solution Implementation

Time and Space Complexity

• Time Complexity: The time complexity is O(2^n), where n is the length of the input string s. This is because each # character could cause the result list to double in length, leading to exponential growth in the number of operations as each character is processed.
• Space Complexity: Ignoring the final answer space, intermediate space usage aside from the result list is O(1). However, the result list itself can grow up to O(2^n) in the worst case due to repeated duplication from the # operation.