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.
Example 1:
Input: s1 = "abc", s2 = "abb", s3 = "ab"
Output: 2
Explanation: 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
Explanation: Since the first letters of s1 and s2 differ, they cannot be made equal.
Constraints:
1 <= s1.length, s2.length, s3.length <= 100s1, s2 and s3 consist only of lowercase English letters.Problem Overview: You are given three strings and can only delete characters from the end of any string. The goal is to make all three strings exactly equal using the minimum number of deletions. If no common string can remain after deletions, return -1.
Approach 1: Common Prefix with Trimming (O(n) time, O(1) space)
Deleting characters only from the end means the final result must be a prefix shared by all three strings. The problem reduces to finding the longest common prefix among the three strings. Iterate character by character while all three strings match at the same index. Stop when a mismatch appears or one string ends. If the longest common prefix length is k, each string must be trimmed to length k, so the total operations equal (len(s1) - k) + (len(s2) - k) + (len(s3) - k). This scan takes linear time proportional to the smallest string length, making it an efficient string traversal problem.
Approach 2: Longest Common Suffix via Reverse Scan (O(n) time, O(1) space)
Another way to reason about the constraint is from the opposite direction. Since deletions happen from the right side, you can repeatedly trim the longest string until all three strings become identical. A practical implementation reverses the strings and computes their longest common suffix (which corresponds to the prefix of the original strings). Iterate with two pointers across the reversed strings and stop when characters differ. The length of this shared suffix determines how many characters can remain in each string. The remaining characters must be deleted. This approach still performs a single linear scan and uses constant extra memory, relying only on simple character comparisons and basic string operations.
Recommended for interviews: The Common Prefix with Trimming approach is what most interviewers expect. It directly models the constraint that deletions happen at the end and leads naturally to the longest common prefix observation. The suffix/reverse method shows the same insight from another perspective and demonstrates strong reasoning about string manipulation. Both achieve optimal O(n) time with O(1) space.
To make all three strings equal, we need to effectively align their tails. A valid equalization would require the remaining parts of each string to be the same, forming a common suffix. We can iterate over the strings from the end towards the beginning and find the longest suffix that is common to all three. The answer will be the total length of the original strings minus three times the length of this common suffix.
This C program calculates the longest common suffix by comparing characters from the end of the strings one by one. It counts how many characters are common in the suffix and calculates the operations required to make the strings equal. A return value of -1 indicates that no common suffix exists.
The time complexity is O(n), where n is the length of the shortest string, because we traverse from the end of each string until we find a mismatch or reach the beginning. The space complexity is O(1), as we use a constant amount of extra space.
This approach involves trimming the strings by checking common prefixes instead of suffixes. The idea is to keep trimming the strings from the start until a common prefix forms among them, and the answer will be the total operations needed to reach one common prefix.
This implementation checks how many characters from the start are identical in all strings. After determining the longest common prefix, it calculates the deletions needed to evenly curve down the strings to the length of this common prefix.
The time complexity is O(n), where n is the smallest string length because each character is checked once. The space complexity is O(1).
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.
The time complexity is O(n), where n is the minimum length of the three strings. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Longest Common Suffix Approach | The time complexity is O(n), where n is the length of the shortest string, because we traverse from the end of each string until we find a mismatch or reach the beginning. The space complexity is O(1), as we use a constant amount of extra space. |
| Common Prefix with Trimming | The time complexity is O(n), where n is the smallest string length because each character is checked once. The space complexity is O(1). |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Common Prefix with Trimming | O(n) | O(1) | Best general solution. Directly models the constraint that only suffix characters can be removed. |
| Longest Common Suffix (Reverse Scan) | O(n) | O(1) | Useful when reasoning from the deletion direction or when implementing reverse string comparisons. |
2937. Make Three Strings Equal || Prefix Check 🔥|| Greedy 🔥 • Ayush Rao • 595 views views
Watch 9 more video solutions →Practice Make Three Strings Equal with our built-in code editor and test cases.
Practice on FleetCode