algoadvance

Leetcode 2937. Make Three Strings Equal

Problem Statement

Given three binary strings s, t, and u, each of the same length, determine if it’s possible to perform zero or more bitwise operations such as AND, OR, and XOR (each given as “&”, “

”, “^” respectively) on pairs of bits in the strings to make all three strings equal.

Example:

Input: s = "101", t = "010", u = "110"
Output: true

Constraints:

• The lengths of the strings are equal.
• The strings are binary (consist of ‘0’ and ‘1’ only).

Clarifying Questions

1. Are the lengths of the strings fixed or can they vary?
   • They are fixed, but all three strings will always have the same length.
2. What operations are allowed?
   • Bitwise AND (&), OR (|), and XOR (^) on pairs of bits in the strings.
3. Can we perform these operations on any pair of bits, or do we need to do them in place within each string?
   • We can perform these operations on any bit across the strings.
4. Is there a limit to the number of operations we can perform?
   • No, as long as it’s possible to make all three strings equal, the number of operations is not limited.

Strategy

To determine if we can make all three strings equal:

• We need to check the conditions resulting from each type of bitwise operation for each corresponding bit in the three strings.
• Consider each bit at position i in s, t, and u.
  • If all three bits are the same (0 or 1), they are already equal.
  • If two bits are 1 and one bit is 0, then we need a combination of operations to turn the 0 into 1.
  • Conversely, if two bits are 0 and one bit is 1, we would need to ensure the bit can be turned into 0.

Conditions:

• For the bits to be equal, at least one of the bits must influence the rest.

Code

Here’s how we can implement this logic in Java:

public class MakeThreeStringsEqual {
    public boolean makeStringsEqual(String s, String t, String u) {
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            int count1 = 0;
            if (s.charAt(i) == '1') count1++;
            if (t.charAt(i) == '1') count1++;
            if (u.charAt(i) == '1') count1++;
            
            if (count1 == 1) {
                return false;  // It's impossible to make all three bits equal if two are 0 and one is 1.
            } // Otherwise (0 or 2 or 3 1s), it's always possible.
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        MakeThreeStringsEqual solution = new MakeThreeStringsEqual();
        
        String s = "101";
        String t = "010";
        String u = "110";
        
        System.out.println(solution.makeStringsEqual(s, t, u)); // Output: true
    }
}

Time Complexity

The time complexity of this solution is O(n) where n is the length of the strings. Each bit position is checked exactly once in each string.

- We loop through each bit position in the strings exactly once.
- The operations within the loop (checking bit values and counting) take constant time.
Therefore, the overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?