Problem Statement in English

You’re given a string s consisting of lowercase English letters and the characters *, #, and %. You are also given an integer k. You need to return the k-th character of the string after processing it with the following operations:

  • “*”: Delete the previous character.
  • “#”: Append the current string to itself.
  • “%”: Reverse the current string.
  • Any other lowercase English letter: Append it to the current string.

Approach

The reason we can’t just simulate in this problem is because the string can get very large (upto $10^15$ according to the constraints), thus we need to find the k-th character without actually constructing the entire string.

Here’s the main problem – when the string is doubled, we have no way of knowing what the k-th character is without knowing the string before it was doubled.

So here’s how we counter that – we process the string in reverse.

This allows us to start with the length of the final string and work our way back to the original string, adjusting k as we go.

This means we need to use the complement of each operation as we iterate through it in reverse:

  • *:
    • Add 1 to the length of the string.
  • #:
    • Either k is in the first half of the string, or it is in the second half. If it is in the second half, we subtract half the length of the string from k and continue – this gives us the position of the character in the string before it was doubled. In either case we also halve the length of the string.
  • %:
    • We take the complement of k with respect to the length of the string, i.e. k = len - 1 - k. The reason we need to do this is because if we haven’t yet found the k-th character, it means that the k-th character is towards the end of the string we’re going toward, which means that the current reverse operation would have changed the position of the k-th character.
  • Any other lowercase English letter: If the length of the string is equal to k + 1, then we have found our character and we return it. Otherwise, we decrement the length of the string by 1.

And we’re done!

Solution in Python


class Solution:
    def processStr(self, s: str, k: int) -> str:
        n = len(s)
        ln = 0

        for c in s:
            if c == '*':
                ln = max(ln - 1, 0)
            elif c == '#':
                ln *= 2
            elif c != '%':
                ln += 1

        if k >= ln:
            return '.'

        for i in reversed(range(n - 1)):
            c = s[i]
            if c == '*':
                ln += 1
            elif c == '#':
                if k >= ln // 2:
                    k -= ln // 2
                ln //= 2
            elif c == '%':
                k = ln - 1 - k
            else:
                if ln == k + 1:
                    return c
                ln -= 1

Complexity

  • Time: $O(n)$
    Since we are iterating through the string s twice, the time complexity is linear with respect to the length of the string.

  • Space: $O(1)$
    Since we are not using any extra space, the space complexity is constant.

Mistakes I Made

I had to look this one up :(

And we are done.