#2546

Medium

auto_awesomeString plus Bit Manipulation

LeetCode Problem Workspace

Apply Bitwise Operations to Make Strings Equal

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

Determine if a binary string s can be transformed into target using repeated bitwise operations on paired indices efficiently.

string bit manipulation

Problem Statement

You are given two binary strings s and target of equal length. You can repeatedly pick two indices i and j, then replace s[i] with s[i] OR s[j] and s[j] with s[i] XOR s[j]. Determine whether it is possible to transform s into target using any number of these operations.

For example, starting with s = '0110', choosing i = 0 and j = 2 updates s[0] to (0 OR 1 = 1) and s[2] to (0 XOR 1 = 1), producing s = '1110'. Return true if s can be made equal to target, otherwise return false.

Examples

Example 1

Input: s = "1010", target = "0110"

Output: true

We can do the following operations:

Choose i = 2 and j = 0. We have now s = "0010".
Choose i = 2 and j = 1. We have now s = "0110". Since we can make s equal to target, we return true.

Example 2

Input: s = "11", target = "00"

Output: false

It is not possible to make s equal to target with any number of operations.

Constraints

n == s.length == target.length
2 <= n <= 105
s and target consist of only the digits 0 and 1.

Solution Approach

Check Presence of Ones

If target contains any '1' but s contains none, transformation is impossible. This immediately rules out invalid cases without simulating operations.

Simulate Necessary Changes

Traverse s and target together. Whenever target[i] is '1', ensure s[i] or some other s[j] is '1' to allow OR operation. No need to simulate every step; presence guarantees feasibility.

Return Feasibility

After verifying that all required ones in target can be matched by s, return true. Otherwise, return false if any required '1' cannot be generated, capturing the problem's primary failure mode.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since we only scan both strings once to check presence of ones and zeros. Space complexity is O(1) if we only track flags for ones in s and target, without extra structures.

What Interviewers Usually Probe

Candidate immediately checks for impossible conversion when s has no ones and target does.
Candidate recognizes OR/XOR operations allow setting zeros to ones but never removing ones without a zero present.
Candidate explains linear scan suffices, no full operation simulation is required.

Common Pitfalls or Variants

Common pitfalls

Forgetting that a string of all zeros cannot produce any ones, leading to incorrect true return.
Attempting full simulation of all operations, which is unnecessary and inefficient.
Misaligning indices when checking feasibility for target ones and s ones.

Follow-up variants

Consider applying similar bitwise operations on integer arrays instead of strings.
Allow operations only on adjacent indices to see how feasibility rules change.
Compute the minimum number of operations required to transform s into target.

FAQ

What is the main idea behind Apply Bitwise Operations to Make Strings Equal?

The core concept is that transforming s to target requires at least one '1' in s to match '1's in target; zeros alone cannot create ones.

Can we simulate every operation to solve this problem?

Full simulation is unnecessary and inefficient; checking presence of ones in s versus target is sufficient.

What failure cases should I watch for?

If target contains a '1' but s has no ones, conversion is impossible. GhostInterview flags this instantly.

Does the order of indices i and j matter?

No, the operation's effect depends on the current values, not the order. Feasibility only depends on ones' availability.

What pattern does this problem primarily test?

It tests the String plus Bit Manipulation pattern, focusing on detecting when bitwise operations cannot achieve the target configuration.

terminal

Solution

Solution 1: Lateral Thinking

We notice that $1$ is actually a "tool" for number conversion. Therefore, as long as both strings either have $1$ or neither have $1$, we can make the two strings equal through operations.

1

2

3

class Solution:
    def makeStringsEqual(self, s: str, target: str) -> bool:
        return ("1" in s) == ("1" in target)

Continue Practicing

#2564 substring xor queries #2506 count pairs of similar strings #2351 first letter to appear twice