Abstract / Summary

Given two binary strings, determine if you can make them equal by performing bitwise operations on both strings the same number of times..

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 43% (50k+ submissions).

Typical patterns to solve this problem:

• Bit Manipulation
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a single method makeStringsEqual that decides whether two binary strings s and target can be made identical using a specific set of bitwise operations. The core of the solution is a concise Boolean expression that captures the necessary condition for transformability. The method returns True when the condition holds and False otherwise.

Core Logic

The algorithm hinges on two observations about the allowed operations:

• Converting a 1 to a 0 requires the presence of another 1 in the source string, because the only way to produce a 0 from a 1 is by applying XOR between two 1s (1 XOR 1 == 0).
• If both strings contain at least one 1, any pattern of bits can be generated by appropriate sequences of OR and XOR operations.

These observations are encoded in the following return statement:

return ("1" in s and "1" in target) or s == target

The expression consists of two parts combined with logical OR:

1. ("1" in s and "1" in target) - checks that each string has at least one 1. When this is true, the algorithm asserts that the transformation is always possible.
2. s == target - handles the situation where the strings are already identical, regardless of their content.

If either part evaluates to True, the method concludes that the strings can be made equal.

Detailed Walkthrough

Presence Check

The first sub-expression uses the membership operator in to scan each string for the character '1'. The evaluation proceeds as follows:

if "1" in s:
    # continue checking target
    if "1" in target:
        # both strings contain a '1'
        return True

Because Python’s and operator short-circuits, the second membership test is performed only when the first test succeeds. This avoids an unnecessary scan of target when s lacks any 1s.

Equality Shortcut

If the presence check fails, the expression falls back to a direct equality comparison:

if s == target:
    return True

When the strings are already the same, no transformation steps are required, and the method can immediately return True.

Final Result

When neither the presence condition nor the equality condition holds, the method returns False. This corresponds to cases where s lacks a 1 but target contains a 1, making it impossible to generate the required 1 bits.

Edge Cases Handled

• Both strings consist solely of 0s - The presence check fails for both strings, but the equality check succeeds, resulting in True.
• Identical strings containing a mixture of 0s and 1s - The equality check short-circuits the evaluation, returning True without examining the presence condition.
• Source string contains at least one 1 while target does not - The presence condition is satisfied because both strings contain a 1 (the source does, the target does not, so the condition fails). The equality check fails, leading to False. This correctly reflects that a 1 cannot be eliminated without another 1 in the source.
• Target string contains a 1 while source does not - The presence condition fails because the source lacks a 1. The equality check also fails, yielding False. This captures the impossibility of creating a 1 from an all-zero source.
• Both strings contain at least one 1 but differ - The presence condition succeeds, and the method returns True, indicating that the required transformations are feasible.

Performance Optimizations

The implementation leverages Python’s built-in string membership test, which scans the string until the first occurrence of '1'. This early-exit behavior minimizes work when a 1 appears near the beginning of the string. The logical and operator further reduces work by preventing the second scan when the first string lacks a 1.

The equality comparison s == target is also optimized by Python: it first checks object identity and length before performing a character-by-character comparison, allowing a fast exit for unequal length strings.

Overall, the method performs at most two linear scans of the input strings, each of which stops as soon as the required condition is met. This yields an efficient solution that scales linearly with the length of the inputs while keeping constant additional memory usage.

Imagine you have two rows of light switches. One row is called the source and the other is called the target. Some switches are flipped up to show a one and some are flipped down to show a zero. You are allowed to take two switches from the source row and change them based on a special rule. If both switches are down, they stay down. If one is up and one is down, you can make them both be up. If both are up, you can make one stay up and turn the other one down.

When you want to see if the source row can eventually look exactly like the target row, you look for a way to use the ones you already have. Because you can use the ones to change other switches, as long as you have at least one switch turned up in both rows, you can reach the target state. If the source row is already a perfect match for the target row, that works out just fine too. The code checks these two simple ideas to see if the transformation is possible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java	C	Go	Rust	TS
	Progiez	C++	Python		Java
github	charles-wangkai				Java
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality