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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Make Three Strings Equal

Number: 3207

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given three strings s1, s2, and s3, you are allowed to delete the rightmost character of any one of these strings in an operation (without completely emptying any string). The goal is to determine the minimum number of operations required to make all three strings equal. If making the strings equal is impossible, return -1.

Key Insights

  • Only prefixes of the original strings can be achieved by deleting characters from the end.
  • The target string must be a common prefix shared by s1, s2, and s3.
  • Maximizing the length of this common prefix minimizes the number of deletions.
  • The total operations required equals the sum of the differences between each string's length and the common prefix length.
  • If there is no common prefix (of at least length 1), then it is impossible to make the strings equal.

Space and Time Complexity

Time Complexity: O(n) where n is the minimum length among s1, s2, and s3. Space Complexity: O(1)

Solution

The solution involves first calculating the length of the common prefix among all three strings. This is done by iterating from the start of the strings until a mismatch is encountered. Let l be the length of this common prefix. If l is greater than 0, then we can trim each string to its prefix of length l. The number of operations required is calculated as (len(s1) - l) + (len(s2) - l) + (len(s3) - l). If l is 0, it means there is no common starting character shared by all the strings, and the answer is -1. This approach uses simple iteration and arithmetic operations while ensuring O(1) space.

Code Solutions

def make_three_strings_equal(s1, s2, s3):
    # Determine the minimum length among the strings to limit the common prefix search
    min_length = min(len(s1), len(s2), len(s3))
    common_prefix_length = 0

    # Find the common prefix by comparing characters at each index
    for i in range(min_length):
        if s1[i] == s2[i] == s3[i]:
            common_prefix_length += 1
        else:
            break

    # If there is no common prefix, return -1 indicating the strings cannot be made equal
    if common_prefix_length == 0:
        return -1

    # Calculate total operations needed by subtracting the common prefix length from each string's length
    operations = (len(s1) - common_prefix_length) + (len(s2) - common_prefix_length) + (len(s3) - common_prefix_length)
    return operations

# Example usage:
print(make_three_strings_equal("abc", "abb", "ab"))  # Expected output: 2
← Back to All Questions