Scale Engineer

Make Three Strings Equal

Easy
#2617Time: O(L_sum * L_max), where `L_sum` is the sum of the initial lengths and `L_max` is the maximum initial length. The `while` loop can run up to `L_sum` times, and inside the loop, `substring` and `equals` operations take up to `O(L_max)` time.Space: O(L_max^2) in Java. In each iteration of the loop, `substring` can create a new string object of up to length `L_max`. Over many iterations, this can lead to significant memory allocation.
Data structures
String

Prompt

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 <= 100
  • s1, s2 and s3 consist only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It repeatedly identifies the longest string among the three and shortens it by one character from the right. This process continues until all three strings become equal. The total number of deletions is calculated based on how many characters were removed from their original lengths.

Algorithm

  • Initialize three pointers, l1, l2, l3, to the lengths of s1, s2, and s3 respectively.
  • Start a loop that continues as long as all three pointers are greater than 0.
  • Inside the loop, check if the prefixes of the strings, defined by the current pointers (s1.substring(0, l1), etc.), are all equal.
    • If they are equal, it means we have found the longest possible common string. The number of operations is the sum of characters removed from each original string: (s1.length() - l1) + (s2.length() - l2) + (s3.length() - l3). Return this value.
  • If the prefixes are not equal, find the maximum length among l1, l2, and l3.
  • Decrement the pointer corresponding to the longest string. If there's a tie for the longest, decrement any one of them.
  • If the loop finishes (meaning one of the pointers became 0) without finding an equal state, it's impossible to make the strings equal. Return -1.

Walkthrough

We use three pointers, l1, l2, and l3, to track the current effective lengths of s1, s2, and s3. We start a loop that continues as long as all strings can potentially form a non-empty common string (i.e., lengths are greater than 0). In each iteration, we first check if the prefixes of the current lengths are equal. If they are, we've found our target common string, and we can calculate the total deletions. If not, we find which of the current lengths is the greatest and decrement it, simulating the removal of a character. If the loop completes because one of the lengths has become zero before a match was found, it's impossible to make them equal. This method is intuitive but inefficient due to the overhead of creating and comparing new substrings in every step of the loop.

class Solution {    public int findMinimumOperations(String s1, String s2, String s3) {        int l1 = s1.length();        int l2 = s2.length();        int l3 = s3.length();         while (l1 > 0 && l2 > 0 && l3 > 0) {            // Check if the current prefixes are equal            // This implies l1, l2, and l3 must be equal for substrings to be equal            if (l1 == l2 && l1 == l3) {                if (s1.substring(0, l1).equals(s2.substring(0, l2)) &&                     s1.substring(0, l1).equals(s3.substring(0, l3))) {                    return (s1.length() - l1) + (s2.length() - l2) + (s3.length() - l3);                }            }                        // If not equal, shorten the longest one            if (l1 >= l2 && l1 >= l3) {                l1--;            } else if (l2 >= l1 && l2 >= l3) {                l2--;            } else {                l3--;            }        }                return -1; // If any string becomes empty before finding a match    }}

Complexity

Time

O(L_sum * L_max), where `L_sum` is the sum of the initial lengths and `L_max` is the maximum initial length. The `while` loop can run up to `L_sum` times, and inside the loop, `substring` and `equals` operations take up to `O(L_max)` time.

Space

O(L_max^2) in Java. In each iteration of the loop, `substring` can create a new string object of up to length `L_max`. Over many iterations, this can lead to significant memory allocation.

Trade-offs

Pros

  • It's a direct simulation of the problem statement, which can be intuitive to conceptualize.

Cons

  • Highly inefficient in both time and space.

  • Involves repeated creation and comparison of substrings, which is computationally expensive.

  • The logic can be more complex to implement correctly compared to the optimal approach.

Solutions

class Solution { public int findMinimumOperations ( String s1 , String s2 , String s3 ) { int s = s1 . length () + s2 . length () + s3 . length (); int n = Math . min ( Math . min ( s1 . length (), s2 . length ()), s3 . length ()); for ( int i = 0 ; i < n ; ++ i ) { if (!( s1 . charAt ( i ) == s2 . charAt ( i ) && s2 . charAt ( i ) == s3 . charAt ( i ))) { return i == 0 ? - 1 : s - 3 * i ; } } return s - 3 * n ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem