Watch 10 video solutions for Make Three Strings Equal, a easy level problem involving String. This walkthrough by Ayush Rao has 595 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |