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: Simulation

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @return {character}
 */
const processStr = function (s, k) {
  const n = s.length;
  const REMOVE = '*';
  const DUPLICATE = '#';
  const REVERSE = '%';
  let len = 0;

  for (const char of s) {
    if (char === REVERSE) continue;

    if (char === REMOVE) {
      len = Math.max(0, len - 1);
    } else if (char === DUPLICATE) {
      len *= 2;
    } else {
      len += 1;
    }
  }

  if (k >= len) return '.';

  for (let index = n - 1; index >= 0; index--) {
    const char = s[index];

    switch (char) {
    case REMOVE: {
      len += 1;
    
    break;
    }
    case DUPLICATE: {
      len = len / 2;

      if (k + 1 > len) {
        k -= len;
      }
    
    break;
    }
    case REVERSE: {
      k = len - k - 1;
    
    break;
    }
    default: {
      if (k + 1 === len) return char;

      len -= 1;
    }
    }
  }

  return '.';
};