easyRecursionPattern: Bit Manipulation
Binary Inverted-Reverse Left Shift Solution
Problem Statement
Given two non-empty binary strings, `initialBinary` and `targetBinary`, determine the minimum non-negative integer `k` such that if `initialBinary` undergoes a specific transformation and then is left-shifted by `k` positions, it becomes exactly equal to `targetBinary`. The transformation involves two steps: 1. **Invert Bits**: Every '0' in `initialBinary` is changed to '1', and every '1' is changed to '0'. 2. **Reverse Bits**: The order of the bits in the inverted string is reversed. If `targetBinary` cannot be formed by applying this transformation and a subsequent left shift for any non-negative `k`, return -1.
Examples
Example 1:
Input:initialBinary = "101", targetBinary = "010"
Output:000000
Explanation: 1. Invert "101": "010"
2. Reverse "010": "010"
3. Left shift "010" by k=0 results in "010", which matches `targetBinary`. The minimum k is 0.
Example 2:
Input:initialBinary = "101", targetBinary = "01000"
Output:000000
Explanation: 1. Invert "101": "010"
2. Reverse "010": "010"
3. Left shift "010" by k=0 -> "010" (no match)
4. Left shift "010" by k=1 -> "0100" (no match)
5. Left shift "010" by k=2 -> "01000" (match!)
The minimum k is 2.
Example 3:
Input:initialBinary = "110", targetBinary = "001"
Output:000000
Explanation: 1. Invert "110": "001"
2. Reverse "001": "100"
3. We need to match "100" shifted by 'k' with "001".
- If k=0, "100" != "001".
- Any positive k will append zeros, making the string longer (e.g., "1000", "10000"), which will never equal "001".
Thus, no non-negative k can make them equal. Return -1.
Constraints
- 1 <= initialBinary.length, targetBinary.length <= 1000
- `initialBinary` and `targetBinary` consist only of '0' or '1' characters.
Time: O(N) Space: O(N)
Initially, perform the bit inversion and reversal on `initialBinary` to obtain `transformedBinary`. If `initialBinary` and `targetBinary` have different lengths, it's impossible. Otherwise, the problem reduces to checking if `targetBinary` is a rotation of `transformedBinary`. This can be efficiently done by concatenating `transformedBinary` with itself (`transformedBinary + transformedBinary`) and then checking if `targetBinary` is a substring of this doubled string. The index of the first occurrence of `targetBinary` in `transformedBinary + transformedBinary` (ensuring it's a valid rotation) gives the minimum `k`.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def transform_binary(binary_string: str) -> str:
inverted_chars = []
for char in binary_string:
inverted_chars.append('1' if char == '0' else '0')
inverted_string = "".join(inverted_chars)
return inverted_string[::-1] # Reverse the string
def solve(initial_binary: str, target_binary: str) -> int:
transformed_binary = transform_binary(initial_binary)
len_transformed = len(transformed_binary)
len_target = len(target_binary)
if len_target < len_transformed:
return -1
# Check if transformed_binary is a prefix of target_binary
if target_binary[:len_transformed] != transformed_binary:
return -1
# Check if the remaining part of target_binary consists only of zeros
for i in range(len_transformed, len_target):
if target_binary[i] == '1':
return -1
return len_target - len_transformed
if __name__ == '__main__':
initial_binary = sys.stdin.readline().strip()
target_binary = sys.stdin.readline().strip()
result = solve(initial_binary, target_binary)
print(result)