Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

• 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;
                  }
              }
          }
      }
  }
  

• 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;
                  }
              }
          }
      }
  };
  

• 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
  
  

• 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
  			}
  		}
  	}
  }
  

• 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;
              }
          }
      }
  }
  
  

All Problems

All Solutions