K-Step Bit Flip with Retention

medium · simulation / string manipulation

You are given a binary string S of length n and a positive integer k. You must apply exactly k transformations to S, one after another. Think of the transformations as being labeled with the values k, k-1, k-2, ..., 1 (the first transformation applied is labeled k, the last is labeled 1). For the transformation labeled with value v, applied to the current string: if v is odd, find the leftmost '1' in the current string — this position is the 'retained' position. If v is even, find the leftmost '0'. If the string has no character of the required type (odd's turn but the string is all '0's, or even's turn but all '1's), retain the last index of the string instead. Then produce the new string by flipping every character ('0' → '1', '1' → '0') except the retained position, which stays unchanged. Repeat for all k labeled transformations (k down to 1) and return the final string. Constraints: 1 ≤ len(s) ≤ 100; 1 ≤ k ≤ 100000. Examples: s = "1010", k = 1 → "1101"; k = 2 → "1111"; k = 3 → "1110"; k = 4 → "1111". Return the final string exactly; there is no alternate output ordering.

Starter code

def k_step_bit_flip(s: str, k: int) -> str:
    """Apply labels k down to 1, retaining the required leftmost bit."""
    pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. The GraderCharacter joke · No posting date

    Edge case? Never met her.

  2. InterviewerCharacter joke · No posting date

    Walk me through your thinking. No, not out loud. In code. In silence. While I watch.

  3. Me at 2amCharacter joke · No posting date

    My code works. I have no idea why. I am afraid to touch it. I am going to bed.