# Make Three Strings Equal
**Difficulty:** EASY
[External](https://leetcode.com/problems/make-three-strings-equal)
Canonical: https://scaleengineer.com/dsa/problems/make-three-strings-equal
**Data structures:** String
---
## Problem
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
## Iterative Shortening (Simulation)
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.
**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.
**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.
### Explanation
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.

```java
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
    }
}
```
### 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.

## Finding Longest Common Prefix (Optimal)
A more efficient approach recognizes that the final equal strings must be a common prefix of the original three strings. To minimize deletions, we need to find the *longest* common prefix. The problem then simplifies to finding the length of this longest common prefix and calculating the total deletions required to trim each string down to it.
**Time:** O(min(L1, L2, L3)), where `L1, L2, L3` are the lengths of the strings. We iterate at most up to the length of the shortest string, performing constant-time operations in each step. · **Space:** O(1). We only use a few integer variables to store lengths and the loop index, requiring constant extra space.
**Pros:** Optimal time complexity, as it only requires a single pass over the strings.; Optimal space complexity, using only a few variables.; The logic is simple, clean, and robust.
**Cons:** Requires a small logical leap to reframe the problem from 'deleting characters' to 'finding a common prefix'.
### Explanation
This method avoids costly string manipulation and focuses on finding the length of the longest common prefix (LCP). We first find the minimum length of the three strings, as the LCP cannot be longer than the shortest string. Then, we iterate with an index `i` from 0 up to this minimum length. In each step, we compare the characters at index `i` of all three strings. If they all match, we continue. The moment we find a mismatch or reach the end of the shortest string, we stop. The value of `i` at that point gives us the length of the LCP.
If the LCP length is 0 (i.e., the first characters don't match), it's impossible to satisfy the condition of non-empty strings, so we return -1. Otherwise, the total number of operations is the sum of the initial lengths minus three times the LCP length.

```java
class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();
        
        int minLen = Math.min(len1, Math.min(len2, len3));
        int commonPrefixLength = 0;
        
        for (int i = 0; i < minLen; i++) {
            if (s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i)) {
                commonPrefixLength++;
            } else {
                break;
            }
        }
        
        if (commonPrefixLength == 0) {
            return -1;
        }
        
        int totalDeletions = (len1 - commonPrefixLength) + (len2 - commonPrefixLength) + (len3 - commonPrefixLength);
        return totalDeletions;
    }
}
```
### Algorithm
- Determine the minimum length among `s1`, `s2`, and `s3`. Let this be `minLen`.
- Initialize a variable `lcpLength = 0` to store the length of the longest common prefix.
- Iterate with an index `i` from `0` to `minLen - 1`.
- In each iteration, check if `s1.charAt(i)`, `s2.charAt(i)`, and `s3.charAt(i)` are all identical.
- If they are, increment `lcpLength`.
- If they are not, break the loop immediately.
- After the loop, check if `lcpLength` is 0. If it is, it means even the first characters did not match, making it impossible. Return -1.
- Otherwise, calculate the total number of deletions: `(s1.length() + s2.length() + s3.length()) - 3 * lcpLength`.
- Return the result.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution { public: int findMinimumOperations ( string s1 , string s2 , string s3 ) { int s = s1 . size () + s2 . size () + s3 . size (); int n = min ({ s1 . size (), s2 . size (), s3 . size ()}); for ( int i = 0 ; i < n ; ++ i ) { if ( ! ( s1 [ i ] == s2 [ i ] && s2 [ i ] == s3 [ i ])) { return i == 0 ? - 1 : s - 3 * i ; } } return s - 3 * n ; } };
```

### Python

```python
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
```