LeetCode 2546 - Apply Bitwise Operations to Make Strings Equal

LeetCode Problem 2546

Difficulty: 🟡 Medium
Topics: String, Bit Manipulation

Solution

Problem Understanding

The problem provides two binary strings, s and target, of equal length n. You are allowed to perform a specific bitwise operation on s any number of times, which involves picking two distinct indices i and j and updating s[i] to s[i] OR s[j] and s[j] to s[i] XOR s[j]. The goal is to determine whether it is possible to transform s into target using this operation.

In simpler terms, you need to check if, by repeatedly combining and swapping bits in s using OR and XOR operations, you can make every bit of s exactly match target. The input strings only contain '0' or '1', and the length can go up to 100,000, so a naive simulation of all operations is impractical.

Key observations from the constraints are that the operation preserves the total number of '1's in a certain sense: if s contains no '1's but target does, the transformation is impossible. The problem also guarantees both strings have length at least 2, which ensures operations involving two indices are always feasible.

Important edge cases include strings with all zeros, strings with all ones, strings with mismatched presence of ones, or strings that are already equal.

Approaches

The brute-force approach would attempt to simulate all possible pairs (i, j) and perform the operation repeatedly until s matches target or no progress can be made. This approach is correct in theory but infeasible for large n because the number of possible operations grows quadratically with the string length and can lead to exponential sequences of operations.

The optimal approach relies on a crucial observation: the operation allows you to propagate '1's across s but cannot create new '1's if none exist. Therefore, the only condition that prevents transformation is if target contains '1' but s has none. Conversely, if s contains at least one '1', it is always possible to spread it and manipulate s to match any target.

This insight reduces the problem to a simple check for the existence of at least one '1' in s if target contains any '1'. No full simulation is needed.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Simulate all operations for all index pairs; too slow for n up to 10^5
Optimal	O(n)	O(1)	Check presence of '1' in s and target; simple and efficient

Algorithm Walkthrough

1. Scan the string target to check if it contains at least one '1'. This is necessary because if target is all zeros, we must ensure s can also become all zeros.
2. Scan the string s to check if it contains at least one '1'. This tells us whether we can propagate '1's in s.
3. If target contains a '1' but s contains no '1's, return false immediately because it is impossible to create new '1's.
4. Otherwise, return true because we can transform s into target using the allowed operations.

Why it works: The operation allows '1's to be propagated to any position via repeated OR/XOR updates. If there is at least one '1' in s, you can eventually reach any configuration of target. If s has no '1's, you cannot create a '1', so any '1' in target makes transformation impossible.

Python Solution

class Solution:
    def makeStringsEqual(self, s: str, target: str) -> bool:
        # Check if target has at least one '1'
        target_has_one = '1' in target
        # Check if s has at least one '1'
        s_has_one = '1' in s
        # If target has '1' but s has none, impossible
        if target_has_one and not s_has_one:
            return False
        return True

The Python implementation directly implements the algorithm. It first checks for the presence of '1' in both strings using the in operator. If target requires at least one '1' but s has none, the function returns False; otherwise, it returns True.

Go Solution

func makeStringsEqual(s string, target string) bool {
    targetHasOne := false
    sHasOne := false

    // Check target for '1'
    for i := 0; i < len(target); i++ {
        if target[i] == '1' {
            targetHasOne = true
            break
        }
    }

    // Check s for '1'
    for i := 0; i < len(s); i++ {
        if s[i] == '1' {
            sHasOne = true
            break
        }
    }

    // If target requires '1' but s has none, impossible
    if targetHasOne && !sHasOne {
        return false
    }
    return true
}

In Go, we iterate over the string as a slice of bytes to check for '1's. The logic mirrors Python's but uses explicit loops since Go does not have a built-in in operator for strings.

Worked Examples

Example 1: s = "1010", target = "0110"

Step	Action	s state	target state
1	Check target for '1'	1010	0110
2	Check s for '1'	1010	0110
3	Both have '1'	1010	0110
4	Return True	1010	0110

Example 2: s = "11", target = "00"

Step	Action	s state	target state
1	Check target for '1'	11	00
2	Check s for '1'	11	00
3	Target has no '1', s has '1'	11	00
4	Return True	11	00

Example 3: s = "00", target = "11"

Step	Action	s state	target state
1	Check target for '1'	00	11
2	Check s for '1'	00	11
3	Target has '1', s has none	00	11
4	Return False	00	11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single scan of both strings to check for '1', each of length n
Space	O(1)	Only a few boolean flags are used, no extra data structures

The complexity is dominated by linear scanning of the strings. No extra storage is needed, so space complexity is constant.

Test Cases

# Provided examples
assert Solution().makeStringsEqual("1010", "0110") == True  # Example 1
assert Solution().makeStringsEqual("11", "00") == True       # Example 2
assert Solution().makeStringsEqual("00", "11") == False      # Example 3

# Boundary values
assert Solution().makeStringsEqual("0"*100000, "0"*100000) == True  # All zeros
assert Solution().makeStringsEqual("1"*100000, "1"*100000) == True  # All ones
assert Solution().makeStringsEqual("0"*99999 + "1", "1"*100000) == True  # Single one in s

# Mixed cases
assert Solution().makeStringsEqual("010101", "101010") == True
assert Solution().makeStringsEqual("000", "001") == False

Test	Why
"1010", "0110"	Standard case with mix of ones and zeros
"11", "00"	Target has no ones, should return True
"00", "11"	Target has ones but s has none, impossible
100000 zeros	Large input, edge case
100000 ones	Large input, should succeed
Single one at end	Propagation of '1' possible
Alternating bits	Mixed propagation scenario
Small zeros vs one	Small impossible case

Edge Cases

The first edge case is when s contains no '1's but target does. This is a failure case because no operations can generate a '1'. The implementation explicitly checks for this scenario and returns False.

The second edge case is when target contains no '1's. Regardless of how many '1's s contains, the transformation is always possible because OR/XOR operations can reduce the bits to zero if needed. The algorithm handles this by simply returning True if target has no '1's.

The third edge case is very large input strings, up to the constraint of 10^5 characters. A naive simulation would be prohibitively slow, but the optimal solution works efficiently because it only