Make Three Strings Equal - Solution & Explanation
Problem Statement
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,s2ands3consist only of lowercase English letters.
Approach Overview
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.
Approach 1: Longest Common Suffix Approach
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.
Complexity
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.
Approach 2: Common Prefix with Trimming
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.
Complexity
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).
Approach 3: 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.
The time complexity is O(n), where n is the minimum length of the three strings. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
2937. Make Three Strings Equal || Prefix Check 🔥|| Greedy 🔥 • Ayush Rao • 598 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Make Three Strings Equal easy or hard?
Make Three Strings Equal Python/Java solution
How to solve Make Three Strings Equal in O(n)?
What is the best approach for Make Three Strings Equal?
Is Make Three Strings Equal asked at Google/Amazon/Meta?
What data structure is used in Make Three Strings Equal?
What is the time complexity of Make Three Strings Equal?
Ready to solve this problem?
Practice Make Three Strings Equal with our built-in code editor and test cases.
Practice on FleetCode