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.

Examples

Example 1

1
2
3
4
5
6
7


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

1
2
3
4
5
6
7


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.

Solution

Method 1 – Greedy: Find Longest Common Prefix

Intuition

To make all three strings equal by only deleting rightmost characters, the only possible result is their longest common prefix. We can only delete characters from the end, so the answer is the total number of characters to delete to make all three strings equal to their common prefix. If there is no common prefix, it’s impossible.

Approach

  1. Find the longest common prefix among s1, s2, and s3.
  2. If the common prefix is empty, return -1.
  3. Otherwise, the answer is the sum of the number of characters to delete from each string to make them equal to the common prefix.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int findMinimumOperations(string s1, string s2, string s3) {
        int n = min({s1.size(), s2.size(), s3.size()});
        int i = 0;
        while (i < n && s1[i] == s2[i] && s2[i] == s3[i]) i++;
        if (i == 0) return -1;
        return (s1.size() - i) + (s2.size() - i) + (s3.size() - i);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func findMinimumOperations(s1, s2, s3 string) int {
    n := min(len(s1), min(len(s2), len(s3)))
    i := 0
    for i < n && s1[i] == s2[i] && s2[i] == s3[i] {
        i++
    }
    if i == 0 {
        return -1
    }
    return (len(s1)-i) + (len(s2)-i) + (len(s3)-i)
}
func min(a, b int) int { if a < b { return a }; return b }
1
2
3
4
5
6
7
8
9

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int n = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
        int i = 0;
        while (i < n && s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i)) i++;
        if (i == 0) return -1;
        return (s1.length() - i) + (s2.length() - i) + (s3.length() - i);
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun findMinimumOperations(s1: String, s2: String, s3: String): Int {
        val n = minOf(s1.length, s2.length, s3.length)
        var i = 0
        while (i < n && s1[i] == s2[i] && s2[i] == s3[i]) i++
        if (i == 0) return -1
        return (s1.length - i) + (s2.length - i) + (s3.length - i)
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
        n = min(len(s1), len(s2), len(s3))
        i = 0
        while i < n and s1[i] == s2[i] and s2[i] == s3[i]:
            i += 1
        if i == 0:
            return -1
        return (len(s1) - i) + (len(s2) - i) + (len(s3) - i)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn find_minimum_operations(s1: String, s2: String, s3: String) -> i32 {
        let n = s1.len().min(s2.len()).min(s3.len());
        let s1b = s1.as_bytes();
        let s2b = s2.as_bytes();
        let s3b = s3.as_bytes();
        let mut i = 0;
        while i < n && s1b[i] == s2b[i] && s2b[i] == s3b[i] {
            i += 1;
        }
        if i == 0 { return -1; }
        (s1.len() - i + s2.len() - i + s3.len() - i) as i32
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    findMinimumOperations(s1: string, s2: string, s3: string): number {
        const n = Math.min(s1.length, s2.length, s3.length);
        let i = 0;
        while (i < n && s1[i] === s2[i] && s2[i] === s3[i]) i++;
        if (i === 0) return -1;
        return (s1.length - i) + (s2.length - i) + (s3.length - i);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the shortest string, since we scan the strings once for the common prefix.
  • 🧺 Space complexity: O(1), only a few variables are used.