Skip to content

3612. Process String with Special Operations I

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 letter is a lowercase English letter append it to result.
  • A '*' removes the last character from result, if it exists.
  • A '#' duplicates the current result and appends it to itself.
  • A '%' reverses the current result.

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

 

Example 1:

Input: s = "a#b%*"

Output: "ba"

Explanation:

i s[i] Operation Current result
0 'a' Append 'a' "a"
1 '#' Duplicate result "aa"
2 'b' Append 'b' "aab"
3 '%' Reverse result "baa"
4 '*' Remove the last character "ba"

Thus, the final result is "ba".

Example 2:

Input: s = "z*#"

Output: ""

Explanation:

i s[i] Operation Current result
0 'z' Append 'z' "z"
1 '*' Remove the last character ""
2 '#' Duplicate the string ""

Thus, the final result is "".

 

Constraints:

  • 1 <= s.length <= 20
  • s consists of only lowercase English letters and special characters *, #, and %.

Solutions

Solution 1: Simulation

We can directly simulate the operations described in the problem. We use a list \(\text{result}\) to store the current result string. For each character in the input string \(s\), we perform the corresponding operation based on the character type:

  • If the character is a lowercase English letter, add it to \(\text{result}\).
  • If the character is *, delete the last character in \(\text{result}\) (if it exists).
  • If the character is #, copy \(\text{result}\) and append it to itself.
  • If the character is %, reverse \(\text{result}\).

Finally, we convert \(\text{result}\) to a string and return it.

The time complexity is \(O(2^n)\), where \(n\) is the length of string \(s\). In the worst case, the # operation may cause the length of \(\text{result}\) to double each time, resulting in exponential time complexity. Ignoring the space consumption of the answer, the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def processStr(self, s: str) -> str:
        result = []
        for c in s:
            if c.isalpha():
                result.append(c)
            elif c == "*" and result:
                result.pop()
            elif c == "#":
                result.extend(result)
            elif c == "%":
                result.reverse()
        return "".join(result)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public String processStr(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) {
                result.append(c);
            } else if (c == '*') {
                result.setLength(Math.max(0, result.length() - 1));
            } else if (c == '#') {
                result.append(result);
            } else if (c == '%') {
                result.reverse();
            }
        }
        return result.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string processStr(string s) {
        string result;
        for (char c : s) {
            if (isalpha(c)) {
                result += c;
            } else if (c == '*') {
                if (!result.empty()) {
                    result.pop_back();
                }
            } else if (c == '#') {
                result += result;
            } else if (c == '%') {
                ranges::reverse(result);
            }
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func processStr(s string) string {
    var result []rune
    for _, c := range s {
        if unicode.IsLetter(c) {
            result = append(result, c)
        } else if c == '*' {
            if len(result) > 0 {
                result = result[:len(result)-1]
            }
        } else if c == '#' {
            result = append(result, result...)
        } else if c == '%' {
            slices.Reverse(result)
        }
    }
    return string(result)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function processStr(s: string): string {
    const result: string[] = [];
    for (const c of s) {
        if (/[a-zA-Z]/.test(c)) {
            result.push(c);
        } else if (c === '*') {
            if (result.length > 0) {
                result.pop();
            }
        } else if (c === '#') {
            result.push(...result);
        } else if (c === '%') {
            result.reverse();
        }
    }
    return result.join('');
}

Comments