Skip to content

2937. Make Three Strings Equal

Description

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.

Solutions

Solution 1: Enumeration

Thinking

Only the last character of one string may be deleted, so the three strings become equal iff they share a nonempty common prefix, which is the final string. Walk index \(i\) until the three characters split; the prefix length is then \(i\).

If \(i=0\) no nonempty equal string exists. Otherwise the deletions equal the total length minus \(3i\). If they never split, use the shortest length. \(n \le 100\) needs one aligned scan.

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)\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func findMinimumOperations(s1 string, s2 string, s3 string) int {
    s := len(s1) + len(s2) + len(s3)
    n := min(len(s1), len(s2), len(s3))
    for i := range s1[:n] {
        if !(s1[i] == s2[i] && s2[i] == s3[i]) {
            if i == 0 {
                return -1
            }
            return s - 3*i
        }
    }
    return s - 3*n
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function findMinimumOperations(s1: string, s2: string, s3: string): number {
    const s = s1.length + s2.length + s3.length;
    const n = Math.min(s1.length, s2.length, s3.length);
    for (let 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;
}

Comments