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.

#2546

Medium

auto_awesomestring·结合·位运算·操作

LeetCode 题解工作台

执行逐位运算使字符串相等

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

给你两个下标从 0 开始的二元字符串 s 和 target ，两个字符串的长度均为 n 。你可以对 s 执行下述操作任意次：选择两个不同的下标 i 和 j ，其中 0 。同时，将 s[i] 替换为 ( s[i] OR s[j] ) ， s[j] 替换为 ( s[i] XOR s[j]…

字符串位运算

题目描述

给你两个下标从 0 开始的二元字符串 s 和 target ，两个字符串的长度均为 n 。你可以对 s 执行下述操作任意次：

选择两个不同的下标 i 和 j ，其中 0 <= i, j < n 。
同时，将 s[i] 替换为 (s[i] OR s[j]) ，s[j] 替换为 (s[i] XOR s[j]) 。

例如，如果 s = "0110" ，你可以选择 i = 0 和 j = 2，然后同时将 s[0] 替换为 (s[0] OR s[2] = 0 OR 1 = 1)，并将 s[2] 替换为 (s[0] XOR s[2] = 0 XOR 1 = 1)，最终得到 s = "1110" 。

如果可以使 s 等于 target ，返回 true ，否则，返回 false 。

示例 1：

输入：s = "1010", target = "0110"
输出：true
解释：可以执行下述操作：
- 选择 i = 2 和 j = 0 ，得到 s = "0010".
- 选择 i = 2 和 j = 1 ，得到 s = "0110".
可以使 s 等于 target ，返回 true 。

示例 2：

输入：s = "11", target = "00"
输出：false
解释：执行任意次操作都无法使 s 等于 target 。

提示：

n == s.length == target.length
2 <= n <= 10⁵
s 和 target 仅由数字 0 和 1 组成

lightbulb

解题思路

方法一：脑筋急转弯

我们注意到 $1$ 其实是数字转换的“工具”，因此只要两个字符串中都有 $1$ 或者都没有 $1$ ，那么就可以通过操作使得两个字符串相等。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串的长度。空间复杂度 $O(1)$ 。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2564 子字符串异或查询 #2506 统计相似字符串对的数目 #2351 第一个出现两次的字母