We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Apply Bitwise Operations to Make Strings Equal

Difficulty: Medium

Problem Description

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]).

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

Key Insights

  • The operation allows transformation of bits in s based on the logical operations OR and XOR.
  • The presence of at least one 1 in s is necessary to convert any 0s to 1s, and vice versa.
  • If both strings have the same number of 1s and 0s (i.e., they are composed of the same bits), it is possible to transform s into target.
  • If s consists entirely of 0s or 1s, it can only be transformed to the same configuration.

Space and Time Complexity

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

Solution

To determine if we can transform s into target, we need to check the following:

  1. Count the number of 1s in both s and target.
  2. If the counts of 1s in s and target are both greater than 0, return true.
  3. If both counts are 0 (both strings are all 0s), return true.
  4. Otherwise, return false.

This approach uses a simple counting mechanism to check the conditions outlined.

Code Solutions

def canMakeEqual(s: str, target: str) -> bool:
    count_s1 = s.count('1')
    count_target1 = target.count('1')
    
    # Both must have the same number of 1's or both must be all 0's
    return (count_s1 > 0 and count_target1 > 0) or (count_s1 == 0 and count_target1 == 0)
← Back to All Questions