algoadvance

Leetcode 2937. Make Three Strings Equal

Problem Statement

You are given three binary strings s1, s2, and target, of the same length. The goal is to make the strings s1 and s2 equal to the target string by performing the following operation any number of times (possibly zero times):

• Pick any character in s1 or s2 and replace it with its complement (‘0’ becomes ‘1’ and ‘1’ becomes ‘0’).

Return true if you can make both s1 and s2 equal to target, and false otherwise.

Clarifying Questions

1. Input Constraints:
   • What are the length constraints of s1, s2, and target?
     • All strings have the same length ( n ) with ( 1 \leq n \leq 10^5 ).
2. Character Set:
   • Can the strings contain characters other than ‘0’ and ‘1’?
     • No, the strings contain only ‘0’ and ‘1’.
3. Operations on the strings:
   • Can we pick any character at any position to flip?
     • Yes, you can flip any character at any position in s1 or s2.

Strategy

To solve this problem, follow these steps:

1. Position Analysis: Compare each character position i of s1, s2, and target.

2. Condition Check: Determine if it’s possible to make both s1[i] and s2[i] equal to target[i]:
   • If target[i] == '0', then both s1[i] and s2[i] should be convertible to ‘0’. This means s1[i] and s2[i] can be either ‘0’ or ‘1’, but not both being ‘1’ at the same time (because flipping one will make it zero).
   • If target[i] == '1', then at least one of s1[i] or s2[i] should be ‘1’.
3. Iteration and Verification: Iterate through each character and check if the above conditions hold for each index. If even one condition fails, return false.

Example Walkthrough

• Example 1:
  • s1 = “1100”, s2 = “1010”, target = “1010”
    • At index 0: target is ‘1’ and one of s1 or s2 has ‘1’, which is valid.
    • At index 1: target is ‘0’ and both s1 and s2 have ‘0’ or one can be made ‘0’; valid.
    • At index 2: target is ‘1’ and one of s1 or s2 has ‘1’; valid.
    • At index 3: target is ‘0’ and both s1 and s2 have ‘0’ or one can be made ‘0’; valid.

Code

#include <iostream>
#include <string>

bool makeStringsEqual(std::string s1, std::string s2, std::string target) {
    int n = s1.size();
    for (int i = 0; i < n; ++i) {
        char t = target[i];
        if (t == '0') {
            if (s1[i] == '1' && s2[i] == '1') {
                return false;
            }
        } else if (t == '1') {
            if (s1[i] == '0' && s2[i] == '0') {
                return false;
            }
        }
    }
    return true;
}

int main() {
    std::string s1 = "1100", s2 = "1010", target = "1010";
    std::cout << std::boolalpha << makeStringsEqual(s1, s2, target) << std::endl; // Output: true

    return 0;
}

Time Complexity

• The time complexity of this solution is ( O(n) ), where ( n ) is the length of the binary strings. This is because we only need to iterate once through the list of characters in the strings to validate the conditions.

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?