3612. Process String with Special Operations I

MediumStringSimulation

Leetcode Link

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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.

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.
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().
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

'a' — It's a lowercase letter. Append it to result: result = ['a']
'b' — Lowercase letter. Append: result = ['a', 'b']
'*' — Remove last character ('b'): result = ['a']
'c' — Lowercase letter. Append: result = ['a', 'c']
'#' — Duplicate current result and append: result = ['a', 'c', 'a', 'c']
'd' — Lowercase letter. Append: result = ['a', 'c', 'a', 'c', 'd']
'%' — 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

1class Solution:
2    def processStr(self, s: str) -> str:
3        # Initialize an empty list to store the processed characters
4        result = []
5        for char in s:
6            if char.isalpha():
7                # If the character is an alphabet, add it to the result
8                result.append(char)
9            elif char == "*" and result:
10                # If the character is '*', remove the last character from result if not empty
11                result.pop()
12            elif char == "#":
13                # If the character is '#', duplicate the current result
14                result.extend(result)
15            elif char == "%":
16                # If the character is '%', reverse the result
17                result.reverse()
18        # Join the list of characters into a string and return it
19        return "".join(result)
20

1class Solution {
2    // Processes a string based on special characters: '*', '#', '%'
3    public String processStr(String s) {
4        StringBuilder result = new StringBuilder();
5
6        // Iterate through each character in the input string
7        for (char ch : s.toCharArray()) {
8            if (Character.isLetter(ch)) {
9                // If the character is a letter, append it to the result
10                result.append(ch);
11            } else if (ch == '*') {
12                // If the character is '*', remove the last character from the result if possible
13                result.setLength(Math.max(0, result.length() - 1));
14            } else if (ch == '#') {
15                // If the character is '#', double the current result
16                result.append(result);
17            } else if (ch == '%') {
18                // If the character is '%', reverse the current result
19                result.reverse();
20            }
21            // All other characters are ignored
22        }
23
24        // Return the processed string
25        return result.toString();
26    }
27}
28

1#include <string>
2#include <algorithm> // For std::reverse
3#include <cctype>    // For std::isalpha
4
5class Solution {
6public:
7    // Processes the input string 's' according to specific rules:
8    // - Append alphabetic characters to the result.
9    // - If '*' is encountered, remove the last character from the result if possible.
10    // - If '#' is encountered, double the content of the result.
11    // - If '%' is encountered, reverse the result.
12    std::string processStr(std::string s) {
13        std::string result;
14        for (char c : s) {
15            if (std::isalpha(c)) {
16                // If character is alphabetic, append to result
17                result += c;
18            } else if (c == '*') {
19                // If '*', remove last character if result is not empty
20                if (!result.empty()) {
21                    result.pop_back();
22                }
23            } else if (c == '#') {
24                // If '#', duplicate the current result
25                result += result;
26            } else if (c == '%') {
27                // If '%', reverse the result
28                std::reverse(result.begin(), result.end());
29            }
30        }
31        return result;
32    }
33};
34

1/**
2 * Processes a given string `s` character by character according to special rules:
3 * - Keeps letters (a-z, A-Z).
4 * - '*' means remove the last character in result if any.
5 * - '#' duplicates the current result and append.
6 * - '%' reverses the whole result.
7 * @param s The input string.
8 * @returns The processed string.
9 */
10function processStr(s: string): string {
11    const result: string[] = []; // Store the processed characters
12
13    for (const char of s) {
14        // Check if current character is a letter
15        if (/[a-zA-Z]/.test(char)) {
16            result.push(char);
17        }
18        // Remove the last character if '*' is encountered
19        else if (char === '*') {
20            if (result.length > 0) {
21                result.pop();
22            }
23        }
24        // Duplicate the current result and append when '#' is found
25        else if (char === '#') {
26            result.push(...result);
27        }
28        // Reverse the entire result array on encountering '%'
29        else if (char === '%') {
30            result.reverse();
31        }
32    }
33
34    // Join result array into a string and return
35    return result.join('');
36}
37

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know