Hard
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:
result
.'*'
removes the last character from result
, if it exists.'#'
duplicates the current result
and appends it to itself.'%'
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
result
after processing s
will not exceed 1015
.public class Solution {
public char processStr(String s, long k) {
long len = 0;
for (char c : s.toCharArray()) {
if (Character.isLowerCase(c)) {
len++;
} else if (c == '*' && len > 0) {
len--;
} else if (c == '#') {
len *= 2;
}
}
if (k >= len) {
return '.';
}
for (int i = s.length() - 1; i >= 0; i--) {
char c = s.charAt(i);
if (Character.isLowerCase(c)) {
if (k == len - 1) {
return c;
}
len--;
} else if (c == '*') {
len++;
} else if (c == '#') {
len /= 2;
if (k >= len) {
k -= len;
}
} else if (c == '%') {
k = len - 1 - k;
}
}
return '.';
}
}