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

Make Three Strings Equal

Difficulty: Easy

Problem Description

You are given three strings: s1, s2, and s3. In one operation you can choose one of these strings and delete its rightmost character. Note that you cannot completely empty a string. Return the minimum number of operations required to make the strings equal. If it is impossible to make them equal, return -1.

Key Insights

  • The goal is to reduce the strings to a common suffix.
  • We can only delete characters from the end of the strings.
  • If the characters at the beginning of any two strings differ, it is impossible to make all three strings equal.
  • The solution involves finding the longest common suffix among the three strings.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the shortest string among the three, since we may need to iterate through each character to find the common suffix. Space Complexity: O(1) since we are using a constant amount of space.

Solution

To solve the problem, we can use the following approach:

  1. Start from the end of each string and compare characters.
  2. Count how many characters match from the end until they differ.
  3. The number of characters that do not match gives us the number of deletions needed.
  4. Calculate the total deletions needed for all three strings to reach the common suffix.

We will utilize a simple loop to find the length of the common suffix and derive the number of operations from the lengths of the original strings.

Code Solutions

def make_equal(s1, s2, s3):
    # Find the length of the common suffix
    def common_suffix_length(s1, s2, s3):
        len_s1, len_s2, len_s3 = len(s1), len(s2), len(s3)
        count = 0
        while (count < len_s1 and count < len_s2 and count < len_s3 and 
               s1[len_s1 - 1 - count] == s2[len_s2 - 1 - count] == s3[len_s3 - 1 - count]):
            count += 1
        return count

    # Length of each string
    len1, len2, len3 = len(s1), len(s2), len(s3)
    
    # Length of the common suffix
    common_length = common_suffix_length(s1, s2, s3)
    
    # Calculate deletions required
    operations = (len1 - common_length) + (len2 - common_length) + (len3 - common_length)
    
    # If the minimum length is less than 1 after operations, it's impossible
    if len1 - operations < 1 or len2 - operations < 1 or len3 - operations < 1:
        return -1
    
    return operations

# Example usage
print(make_equal("abc", "abb", "ab"))  # Output: 2
print(make_equal("dac", "bac", "cac"))  # Output: -1
← Back to All Questions