K-Step Bit Flip with Retention
Updated
Problem statement
You are given a binary string s and a positive integer k. Apply exactly k steps to s, one after another. The steps are labeled k, k - 1, k - 2, ..., 1. The first step has label k, and the last step has label 1.
A step with label v changes the current string in two parts:
- Choose the kept position:
- If
vis odd, it is the position of the leftmost'1'. - If
vis even, it is the position of the leftmost'0'. - If the string has no character of that kind, it is the last position,
s.length - 1.
- If
- Flip every character except the one at the kept position. A
'0'becomes'1', and a'1'becomes'0'. The kept character stays the same.
Positions are counted from 0. Return the string after all k steps.
Function
kStepBitFlip(s: String, k: int) → StringExamples
Example 1
s = "1010"k = 1return = "1101"There is one step, with label 1. The label is odd, so the kept position is the leftmost '1', at index 0. Every other character flips, so "1010" becomes "1101".
Example 2
s = "1010"k = 2return = "1111"The labels are 2, then 1.
- Label
2is even. The leftmost'0'is at index1, so it is kept and the rest flip:"1010"becomes"0001". - Label
1is odd. The leftmost'1'is at index3, so it is kept:"0001"becomes"1111".
Example 3
s = "1010"k = 3return = "1110"The labels are 3, 2, then 1.
- Label
3is odd. Keep index0:"1010"becomes"1101". - Label
2is even. Keep index2, the leftmost'0':"1101"becomes"0000". - Label
1is odd, but there is no'1'. Keep the last index,3:"0000"becomes"1110".
Example 4
s = "1010"k = 4return = "1111"The labels are 4, 3, 2, then 1.
- Label
4is even. Keep index1:"1010"becomes"0001". - Label
3is odd. Keep index3, the only'1':"0001"becomes"1111". - Label
2is even, but there is no'0'. Keep the last index,3:"1111"becomes"0001". - Label
1is odd. Keep index3:"0001"becomes"1111".
Example 5
s = "001"k = 1000000000return = "111"The first label, 10^9, is even. Keep index 0: "001" becomes "010".
The next label is odd. Keep index 1, the leftmost '1': "010" becomes "111".
From here on, every step keeps the last index. An even label finds no '0', and an odd label finds its leftmost '1' at index 2. So the string goes "111", "001", "111", "001", and so on. It is "111" after every even number of steps. 10^9 is even, so the answer is "111".
Constraints
1 <= s.length <= 10^4scontains only the characters'0'and'1'.1 <= k <= 10^9
More Cisco interview questions
- Check if a String Is a PalindromePHONE SCREEN · Seen Nov 2026
- Find Unique ElementsPHONE SCREEN · Seen Nov 2026
- First Letter to Appear TwicePHONE SCREEN · Seen Nov 2026
- Middle of a Linked ListPHONE SCREEN · Seen Nov 2026
- Reverse a Linked ListPHONE SCREEN · Seen Nov 2026
- Reverse a StringPHONE SCREEN · Seen Nov 2026
- Valid ParenthesesPHONE SCREEN · Seen Nov 2026
- Longest Non-Repeating SubstringPHONE SCREEN · Seen Jul 2026
- Todo Task Manager OperationsONSITE INTERVIEW · Seen Oct 2026
- Find the Duplicate Number Without Modifying the ArrayONSITE INTERVIEW · Seen Sep 2026
Similar questions at other companies
- Business Account KYC Verification — Parts 1–5Stripe · PHONE SCREENStripe interview questions
- Read Across Sound TracksAirbnb · PHONE SCREENAirbnb interview questions
- Stateful Log Transform and SearchRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Elevator Scheduling SimulationOpenAI · PHONE SCREENOpenAI interview questions
- File Storage ServiceCresta · PHONE SCREENCresta interview questions
- String Interpolation with a Missing-Value ModeMongoDB · PHONE SCREENMongoDB interview questions
- Dasher Pay with Store Waits and Peak HoursDoorDash · PHONE SCREENDoorDash interview questions
- Return Every Matching DecryptionDuolingo · PHONE SCREENDuolingo interview questions
- Fixed-Order Task Run Time With CooldownWaymo · PHONE SCREENWaymo interview questions