#2937

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Make Three Strings Equal

Determine the minimum number of operations to make three strings equal by removing rightmost characters from one string at a time.

string

Problem Statement

You are given three strings: s1, s2, and s3. You can perform one operation at a time by deleting the rightmost character of one of the strings. Your goal is to make all three strings equal by performing the fewest operations. Note that you cannot fully empty any of the strings.

Return the minimum number of operations required to make the strings equal. If it is impossible to make the strings equal, return -1. For example, if the strings 'abc', 'abb', and 'ab' are given, you can delete the rightmost character of both 'abc' and 'abb' to make all three strings equal to 'ab'.

Examples

Example 1

Input: s1 = "abc", s2 = "abb", s3 = "ab"

Output: 2

Deleting the rightmost character from both s1 and s2 will result in three equal strings.

Example 2

Input: s1 = "dac", s2 = "bac", s3 = "cac"

Output: -1

Since the first letters of s1 and s2 differ, they cannot be made equal.

Constraints

1 <= s1.length, s2.length, s3.length <= 100
s1, s2 and s3 consist only of lowercase English letters.

Solution Approach

Find the Longest Common Prefix

The first step is to determine the longest common prefix of the three strings. This will be the target string that all strings need to become equal to.

Calculate Differences from the Prefix

For each string, calculate the number of characters that need to be deleted by subtracting the length of the common prefix from the length of the string.

Handle Edge Cases

Check for cases where it is impossible to make the strings equal, such as when no common prefix exists. In such cases, return -1.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the longest common prefix calculation and the lengths of the strings. Since we are iterating over the characters of the strings once, the time complexity is O(n), where n is the length of the longest string. The space complexity is O(1) as no additional space is needed except for a few variables.

What Interviewers Usually Probe

Look for a solution that efficiently calculates the longest common prefix of the three strings.
Evaluate if the candidate handles edge cases, such as strings that cannot be made equal.
Consider how the candidate approaches calculating the necessary deletions and the final result.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution with unnecessary operations or nested loops.
Failing to account for edge cases, such as strings with no common prefix.
Not optimizing for time complexity, especially when dealing with strings of varying lengths.

Follow-up variants

The problem can be extended to handle more than three strings.
A variant could involve restricting the number of deletions per string.
Another variant might require making the strings equal by removing characters from both ends instead of just the right side.

FAQ

How do I approach the 'Make Three Strings Equal' problem?

Start by calculating the longest common prefix for the three strings. Then, determine how many characters need to be removed from each string to make them equal.

What happens if there is no common prefix?

If no common prefix exists, it's impossible to make the strings equal, and the answer should be -1.

Is it necessary to delete characters from the end of the strings?

Yes, the problem specifically requires you to delete characters from the rightmost end of the strings to make them equal.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the longest string, due to the need to find the longest common prefix and calculate the deletions.

Can this problem be solved if we have more than three strings?

Yes, you can extend the solution to handle more than three strings by calculating the longest common prefix among all the strings and then applying the same deletion strategy.

terminal

Solution

Solution 1: Enumeration

According to the problem description, we know that if the three strings are equal after deleting characters, then they have a common prefix of length greater than $1$. Therefore, we can enumerate the position $i$ of the common prefix. If the three characters at the current index $i$ are not all equal, then the length of the common prefix is $i$. At this point, we check if $i$ is $0$. If it is, return $-1$. Otherwise, return $s - 3 \times i$, where $s$ is the sum of the lengths of the three strings.

1

2

3

4

5

6

7

8

class Solution:
    def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
        s = len(s1) + len(s2) + len(s3)
        n = min(len(s1), len(s2), len(s3))
        for i in range(n):
            if not s1[i] == s2[i] == s3[i]:
                return -1 if i == 0 else s - 3 * i
        return s - 3 * n

Continue Practicing

#2938 separate black and white balls #2933 high access employees #2942 find words containing character