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 fromresult, if it exists. - A
'#'duplicates the currentresultand appends it to itself. - A
'%'reverses the currentresult.
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 <= 105sconsists of only lowercase English letters and special characters'*','#', and'%'.0 <= k <= 1015- The length of
resultafter processingswill not exceed1015.
Solutions
This function finds the character at a specific index k in a virtual text that is dynamically built by interpreting the string s as a sequence of editing commands: normal letters append to the text, * acts as a backspace, # duplicates the text generated so far, and % reverses its order. To avoid the massive memory cost of actually building this potentially giant virtual text, the code first loops forward to calculate its final length. It then loops backward through the commands to reverse-engineer the operations, tracking and shifting the target index k backward step-by-step until it pinpoints and returns the exact physical character that lands at that position, returning . if the index is out of bounds.
/**
* @param {string} s
* @param {number} k
* @return {character}
*/
var processStr = function(s, k) {
let len = 0;
for (const char of s) {
if (char === '*') {
if (len > 0) {
len--;
}
} else if (char === '#') {
len *= 2;
} else if (char === '%') {
// do nothing
} else {
len++;
}
}
if (k >= len) {
return '.';
}
for (let i = s.length - 1; i >= 0; i--) {
const char = s[i];
if (char === '*') {
len++;
} else if (char === '#') {
if (k > (len - 1) / 2) {
k -= Math.floor(len / 2);
}
len = Math.floor((len + 1) / 2);
} else if (char === '%') {
k = len - 1 - k;
} else {
if (k === len - 1) {
return char;
}
len--;
}
}
return '.';
};