2546. Apply Bitwise Ops to Make Strings Equal Solution

Q: Is Apply Bitwise Operations to Make Strings Equal easy or hard?

The problem is rated Medium because the implementation is simple but the insight about bitwise invariants is not immediately obvious. Many candidates initially try to simulate operations, but the correct solution comes from recognizing that the existence of a '1' cannot be created from zero or completely removed.

Q: Apply Bitwise Operations to Make Strings Equal Python/Java solution

In Python or Java, the implementation usually checks whether '1' appears in each string using built‑in string search functions. For example, in Python you can use `'1' in s` and `'1' in target`. In Java, use `s.contains("1")`. If both results match, return true; otherwise return false.

Q: How to solve Apply Bitwise Operations to Make Strings Equal in O(n)?

Scan both strings and determine whether each contains at least one '1'. If both have a '1', you can use OR to spread that bit and XOR to flip positions to match the target. If neither string has a '1', both are already all zeros and therefore equalizable. If exactly one string contains a '1', the transformation is impossible.

Q: What is the best approach for Apply Bitwise Operations to Make Strings Equal?

The optimal approach checks whether both strings contain at least one '1'. Bitwise OR can spread a 1 across positions, and XOR can flip bits when another 1 exists. However, you cannot create the first 1 from all zeros or remove the last remaining 1. Therefore, the transformation is possible only if both strings either contain a '1' or both contain none. This runs in O(n) time and O(1) space.

Q: Is Apply Bitwise Operations to Make Strings Equal asked at Google/Amazon/Meta?

Problems involving bit manipulation and transformation invariants are common in interviews at companies like Google, Amazon, and Meta. This specific question tests reasoning about OR and XOR behavior rather than implementation complexity, which is a pattern frequently seen in technical screens.

Q: What data structure is used in Apply Bitwise Operations to Make Strings Equal?

No complex data structure is required. The solution works directly on the input strings and uses simple boolean checks to determine whether a '1' exists. The focus is on understanding bitwise operations rather than using additional storage.

Q: What is the time complexity of Apply Bitwise Operations to Make Strings Equal?

The optimal solution runs in O(n) time where n is the length of the binary strings. You only scan each string once to check whether it contains a '1'. The space complexity is O(1) because the algorithm stores only a few boolean flags.

The problem

You are given two 0-indexed binary strings s and target of the same length n. You can do the following operation on s any number of times:

Choose two different indices i and j where 0 <= i, j < n.
Simultaneously, replace s[i] with (s[i] OR s[j]) and s[j] with (s[i] XOR s[j]).

For example, if s = "0110", you can choose i = 0 and j = 2, then simultaneously replace s[0] with (s[0] OR s[2] = 0 OR 1 = 1), and s[2] with (s[0] XOR s[2] = 0 XOR 1 = 1), so we will have s = "1110".

Return true if you can make the string s equal to target, or false otherwise.

Example 1:

Input: s = "1010", target = "0110"
Output: true
Explanation: 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
Explanation: It is not possible to make s equal to target with any number of operations.

Constraints:

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

Approach overview

Problem Overview: You are given two binary strings s and target. You can repeatedly choose two different indices and replace s[i] with either s[i] OR s[j] or s[i] XOR s[j]. The goal is to determine whether these operations can transform s into target.

Approach 1: Count Ones and Zeros (O(n) time, O(1) space)

Iterate through both strings and count the number of '1' characters. The key observation comes from how the allowed operations behave. OR can spread a 1 to other positions, while XOR can flip bits if another 1 exists in the string. Because of this, once a string contains at least one 1, you can propagate or flip bits to build any configuration that also contains a 1. However, if the string contains no 1, all operations keep it zero forever. The transformation is possible only when both strings either contain at least one 1 or both contain none. Counting provides a straightforward way to check this condition.

This method performs a single pass through each string, using constant memory. The counts themselves are not strictly required beyond determining whether a 1 exists, but they make the reasoning explicit and easy to verify.

Approach 2: Presence of Both Digits (O(n) time, O(1) space)

The optimal approach simplifies the previous idea even further. Instead of counting, check whether each string contains at least one '1'. The allowed operations create a useful invariant: you cannot generate the first 1 if the string starts with all zeros, and you cannot eliminate the final 1 once it exists. This means the existence of a 1 in the string never changes from zero to non‑zero or vice versa.

Compute hasOneS = s.contains('1') and hasOneT = target.contains('1'). If both values match, the transformation is possible. If one string has a 1 and the other does not, no sequence of operations can bridge that gap.

This solution uses a single linear scan and constant extra space. The reasoning relies on understanding how bitwise operations propagate bits, which makes it a good exercise when practicing bit manipulation and string processing problems.

Recommended for interviews: The presence-check approach is what most interviewers expect. It shows that you recognized the invariant created by the bitwise operations rather than simulating transformations. A counting version demonstrates the same idea but is slightly more verbose. The optimal insight—checking whether both strings share the same "contains 1" state—demonstrates strong reasoning about bitwise operations.

Approach 1: Approach 1: Count Ones and Zeros

This approach is based on the idea that, to convert the string s to the target using the described operations, you need to either transform a '0' to a '1' or ensure both strings already match with respect to the position's bits. To achieve a target, the count of '1's in both strings must match, as the operations cannot increase or decrease the total count of '1's.

Python

def canMakeStringsEqual(s: str, target: str) -> bool:
    return s.count('1') == target.count('1')

Java

public class Solution {
    public boolean canMakeStringsEqual(String s, String target) {
        int count1_s = 0, count1_target = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') count1_s++;
            if (target.charAt(i) == '1') count1_target++;
        }
        return count1_s == count1_target;
    }
}

C++

#include <string>

bool canMakeStringsEqual(std::string s, std::string target) {
    int count1_s = std::count(s.begin(), s.end(), '1');
    int count1_target = std::count(target.begin(), target.end(), '1');
    return count1_s == count1_target;
}

JavaScript

function canMakeStringsEqual(s, target) {
    const count1_s = (s.match(/1/g) || []).length;
    const count1_target = (target.match(/1/g) || []).length;
    return count1_s === count1_target;
}

#include <stdbool.h>
#include <string.h>

bool canMakeStringsEqual(char *s, char *target) {
    int count1_s = 0, count1_target = 0;
    for (int i = 0; i < strlen(s); ++i) {
        if (s[i] == '1') count1_s++;
        if (target[i] == '1') count1_target++;
    }
    return count1_s == count1_target;
}

public class Solution {
    public bool CanMakeStringsEqual(string s, string target) {
        int count1_s = s.Count(c => c == '1');
        int count1_target = target.Count(c => c == '1');
        return count1_s == count1_target;
    }
}

The Python solution makes use of the in-built count function to count '1's in s and target and checks if they are equal.

Complexity

Time Complexity: O(n) | Space Complexity: O(1)

Try this approach in the editor

Approach 2: Approach 2: Presence of Both Digits

The critical observation here is that the operations allow us to swap '0' to '1' and vice versa, provided both '1' and '0' exist in the string. It is possible to make the transformation if and only if both strings have at least one '1' and at least one '0', or they are already identical.

Python

def canMakeStringsEqual(s: str, target: str) -> bool:
    if s == target:
        return True
    return '0' in s and '1' in s

Java

public class Solution {
    public boolean canMakeStringsEqual(String s, String target) {
        if (s.equals(target)) return true;
        boolean hasZero = false, hasOne = false;
        for (char c : s.toCharArray()) {
            if (c == '0') hasZero = true;
            if (c == '1') hasOne = true;
        }
        return hasZero && hasOne;
    }
}

C++

#include <string>

bool canMakeStringsEqual(std::string s, std::string target) {
    if (s == target) return true;
    bool hasZero = false, hasOne = false;
    for (char c : s) {
        if (c == '0') hasZero = true;
        if (c == '1') hasOne = true;
    }
    return hasZero && hasOne;
}

JavaScript

function canMakeStringsEqual(s, target) {
    if (s === target) return true;
    return s.includes('0') && s.includes('1');
}

#include <stdbool.h>
#include <string.h>

bool canMakeStringsEqual(char *s, char *target) {
    if (strcmp(s, target) == 0) return true;
    bool hasZero = false, hasOne = false;
    for (int i = 0; i < strlen(s); ++i) {
        if (s[i] == '0') hasZero = true;
        if (s[i] == '1') hasOne = true;
    }
    return hasZero && hasOne;
}

public class Solution {
    public bool CanMakeStringsEqual(string s, string target) {
        if (s == target) return true;
        bool hasZero = false, hasOne = false;
        foreach (char c in s) {
            if (c == '0') hasZero = true;
            if (c == '1') hasOne = true;
        }
        return hasZero && hasOne;
    }
}

The Python solution uses a direct equality comparison and a membership test to check for '0' and '1' in s.

Complexity

Time Complexity: O(n) | Space Complexity: O(1)

Try this approach in the editor

Approach 3: 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.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

TypeScript

function makeStringsEqual(s: string, target: string): boolean {
    return s.includes('1') === target.includes('1');
}

func makeStringsEqual(s string, target string) bool {
	return strings.Contains(s, "1") == strings.Contains(target, "1")
}

Rust

impl Solution {
    pub fn make_strings_equal(s: String, target: String) -> bool {
        s.contains('1') == target.contains('1')
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Count Ones and Zeros	Time Complexity: O(n) \| Space Complexity: O(1)
Approach 2: Presence of Both Digits	Time Complexity: O(n) \| Space Complexity: O(1)
Lateral Thinking	–

Complexity analysis

Approach	Time	Space	When to Use
Count Ones and Zeros	O(n)	O(1)	Good for explaining the reasoning step‑by‑step by explicitly counting digits in both strings.
Presence of Both Digits	O(n)	O(1)	Best practical solution. Only checks whether each string contains at least one '1'.

Frequently asked questions

Is Apply Bitwise Operations to Make Strings Equal easy or hard?

The problem is rated Medium because the implementation is simple but the insight about bitwise invariants is not immediately obvious. Many candidates initially try to simulate operations, but the correct solution comes from recognizing that the existence of a '1' cannot be created from zero or completely removed.

Apply Bitwise Operations to Make Strings Equal Python/Java solution

In Python or Java, the implementation usually checks whether '1' appears in each string using built‑in string search functions. For example, in Python you can use `'1' in s` and `'1' in target`. In Java, use `s.contains("1")`. If both results match, return true; otherwise return false.

How to solve Apply Bitwise Operations to Make Strings Equal in O(n)?

Scan both strings and determine whether each contains at least one '1'. If both have a '1', you can use OR to spread that bit and XOR to flip positions to match the target. If neither string has a '1', both are already all zeros and therefore equalizable. If exactly one string contains a '1', the transformation is impossible.

What is the best approach for Apply Bitwise Operations to Make Strings Equal?

The optimal approach checks whether both strings contain at least one '1'. Bitwise OR can spread a 1 across positions, and XOR can flip bits when another 1 exists. However, you cannot create the first 1 from all zeros or remove the last remaining 1. Therefore, the transformation is possible only if both strings either contain a '1' or both contain none. This runs in O(n) time and O(1) space.

Is Apply Bitwise Operations to Make Strings Equal asked at Google/Amazon/Meta?

Problems involving bit manipulation and transformation invariants are common in interviews at companies like Google, Amazon, and Meta. This specific question tests reasoning about OR and XOR behavior rather than implementation complexity, which is a pattern frequently seen in technical screens.

What data structure is used in Apply Bitwise Operations to Make Strings Equal?

No complex data structure is required. The solution works directly on the input strings and uses simple boolean checks to determine whether a '1' exists. The focus is on understanding bitwise operations rather than using additional storage.

What is the time complexity of Apply Bitwise Operations to Make Strings Equal?

The optimal solution runs in O(n) time where n is the length of the binary strings. You only scan each string once to check whether it contains a '1'. The space complexity is O(1) because the algorithm stores only a few boolean flags.

Apply Bitwise Operations to Make Strings Equal solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Count Ones and Zeros

Approach 2: Approach 2: Presence of Both Digits

Approach 3: Lateral Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Apply Bitwise Operations to Make Strings Equal solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Count Ones and Zeros

Approach 2: Approach 2: Presence of Both Digits

Approach 3: Lateral Thinking

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems