0840HardStringSimulation

Character at a Slot of the Built Tape

Tracked in this browser only

Trains the technique from

LeetCode 3614Process String with Special Operations II

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape starts empty. The string s is read left to right, one character at a time, and each character is an instruction:

a lowercase letter appends that letter to the end of the tape;
'*' removes the last character of the tape, and does nothing when the tape is already empty;
'#' appends a copy of the whole tape to itself, so the tape doubles in length;
'%' reverses the tape.

Return the character sitting at slot k of the finished tape, counting slots from 0. If the finished tape holds k characters or fewer, return "." instead.

Examples

Example 1

Input: s = "ab#", k = 3
Output: "b"

The tape reads "ab" after two letters, then doubling makes it "abab". Slot 3 of that tape holds "b".

Example 2

Input: s = "ab%", k = 0
Output: "b"

Reversing "ab" gives "ba", so slot 0 holds "b".

Example 3

Input: s = "a", k = 1
Output: "."

The finished tape holds one character, so slot 1 is past its end and the answer is ".".

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters and the characters '*', '#' and '%' only
0 <= k <= 1000000000000000
The finished tape never holds more than 10^15 characters

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def char_at_position(s: str, k: int) -> str:

Java

public char charAtPosition(String s, long k)

The intended approach

Time O(L) for L instructions: one forward sweep for the lengths and one backward walk.Space O(L) for the recorded lengths.

The tape can grow to a size no machine would hold, so it is never built. Sweep the instructions once recording the tape's length after each step, capping the running length so a run of doublings cannot produce an unbounded number. Then walk the instructions backwards carrying the slot being asked about. A doubling means a slot in the second half came from the same slot of the first half, so subtract the length before that step. A reversal flips the slot within the length before that step. A delete leaves earlier slots alone. A letter occupies the very last slot at its own step, so if the carried slot has reached there, that letter is the answer.

Pythonentry point: char_at_position

def char_at_position(s, k):
    # measure the tape's finished length step by step, capping the running length
    # so it cannot run away, then walk the steps backwards to place k
    CAP = 10 ** 15 + 10
    lengths = [0]
    size = 0
    for ch in s:
        if ch == "*":
            if size > 0:
                size -= 1
        elif ch == "#":
            size = size * 2
            if size > CAP:
                size = CAP
        elif ch == "%":
            pass
        else:
            size += 1
        lengths.append(size)

    if k >= lengths[-1]:
        return "."

    pos = k
    for idx in range(len(s) - 1, -1, -1):
        ch = s[idx]
        before = lengths[idx]
        if ch == "*":
            continue
        if ch == "#":
            if pos >= before:
                pos -= before
            continue
        if ch == "%":
            pos = before - 1 - pos
            continue
        # a plain letter: it sits at the very end of the tape at this step
        if pos == before:
            return ch
    return "."

The obvious version

Build the tape literally, applying each instruction to a list, then read off the slot. Only usable when the instructions keep the tape small, but it needs no reasoning about where a slot came from.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_char_at_position(s, k):
    tape = []
    for ch in s:
        if ch == "*":
            if tape:
                tape.pop()
        elif ch == "#":
            tape = tape + tape
        elif ch == "%":
            tape.reverse()
        else:
            tape.append(ch)
    if k >= len(tape):
        return "."
    return tape[k]

How this problem was checked

Reference solution executed against 19 test cases — 19 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in