Skip to content

3614. Process String with Special Operations II

Description

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

You are also given an integer k.

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 kth character of the final string result. If k is out of the bounds of result, return '.'.

Β 

Example 1:

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

Output: "a"

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"

The final result is "ba". The character at index k = 1 is 'a'.

Example 2:

Input: s = "cd%#*#", k = 3

Output: "d"

Explanation:

i s[i] Operation Current result
0 'c' Append 'c' "c"
1 'd' Append 'd' "cd"
2 '%' Reverse result "dc"
3 '#' Duplicate result "dcdc"
4 '*' Remove the last character "dcd"
5 '#' Duplicate result "dcddcd"

The final result is "dcddcd". The character at index k = 3 is 'd'.

Example 3:

Input: s = "z*#", k = 0

Output: "."

Explanation:

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

The final result is "". Since index k = 0 is out of bounds, the output is '.'.

Β 

Constraints:

  • 1 <= s.length <= 105
  • s consists of only lowercase English letters and special characters '*', '#', and '%'.
  • 0 <= k <= 1015
  • The length of result after processing s will not exceed 1015.

Solutions

Solution 1: Reverse Tracking

We first calculate the length \(m\) of the processed result string \(\textit{result}\). If \(k \geq m\), it indicates that \(k\) exceeds the valid indices of the result string, so we return '.'.

Otherwise, we traverse the string \(s\) in reverse order and handle each character based on the following cases:

  1. If \(s[i]\) is '*', we increase \(m\) by \(1\).
  2. If \(s[i]\) is '#', we divide \(m\) by \(2\). At this point, if \(k \geq m\), we subtract \(m\) from \(k\).
  3. If \(s[i]\) is '%', we update \(k\) to \(m - 1 - k\).
  4. Otherwise, \(s[i]\) is a letter. We decrease \(m\) by \(1\). If \(k = m\), it means we have found the \(k\)-th character, so we return \(s[i]\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def processStr(self, s: str, k: int) -> str:
        m = 0
        for c in s:
            if c == "*":
                m = max(0, m - 1)
            elif c == "#":
                m <<= 1
            elif c != "%":
                m += 1
        if k >= m:
            return "."
        for c in reversed(s):
            if c == "*":
                m += 1
            elif c == "#":
                m //= 2
                if k >= m:
                    k -= m
            elif c == "%":
                k = m - 1 - k
            else:
                m -= 1
                if k == m:
                    return c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public char processStr(String s, long k) {
        long m = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '*') {
                m = Math.max(0, m - 1);
            } else if (c == '#') {
                m <<= 1;
            } else if (c != '%') {
                m += 1;
            }
        }
        if (k >= m) {
            return '.';
        }
        for (int i = s.length() - 1;; i--) {
            char c = s.charAt(i);
            if (c == '*') {
                m += 1;
            } else if (c == '#') {
                m /= 2;
                if (k >= m) {
                    k -= m;
                }
            } else if (c == '%') {
                k = m - 1 - k;
            } else {
                m -= 1;
                if (k == m) {
                    return c;
                }
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    char processStr(string s, long long k) {
        long long m = 0;
        for (char c : s) {
            if (c == '*') {
                m = max(0LL, m - 1);
            } else if (c == '#') {
                m <<= 1;
            } else if (c != '%') {
                m += 1;
            }
        }
        if (k >= m) {
            return '.';
        }
        for (int i = s.length() - 1;; i--) {
            char c = s[i];
            if (c == '*') {
                m += 1;
            } else if (c == '#') {
                m /= 2;
                if (k >= m) {
                    k -= m;
                }
            } else if (c == '%') {
                k = m - 1 - k;
            } else {
                m -= 1;
                if (k == m) {
                    return c;
                }
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func processStr(s string, k int64) byte {
    var m int64 = 0
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c == '*' {
            if m-1 > 0 {
                m = m - 1
            } else {
                m = 0
            }
        } else if c == '#' {
            m <<= 1
        } else if c != '%' {
            m += 1
        }
    }
    if k >= m {
        return '.'
    }
    for i := len(s) - 1; ; i-- {
        c := s[i]
        if c == '*' {
            m += 1
        } else if c == '#' {
            m /= 2
            if k >= m {
                k -= m
            }
        } else if c == '%' {
            k = m - 1 - k
        } else {
            m -= 1
            if k == m {
                return c
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function processStr(s: string, k: number): string {
    let m = 0n;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c === '*') {
            const sub = m - 1n;
            m = sub > 0n ? sub : 0n;
        } else if (c === '#') {
            m <<= 1n;
        } else if (c !== '%') {
            m += 1n;
        }
    }
    if (BigInt(k) >= m) {
        return '.';
    }
    let bigK = BigInt(k);
    for (let i = s.length - 1; ; i--) {
        const c = s[i];
        if (c === '*') {
            m += 1n;
        } else if (c === '#') {
            m /= 2n;
            if (bigK >= m) {
                bigK -= m;
            }
        } else if (c === '%') {
            bigK = m - 1n - bigK;
        } else {
            m -= 1n;
            if (bigK === m) {
                return c;
            }
        }
    }
}

Comments