LeetCode 2937 - Make Three Strings Equal

LeetCode Problem 2937

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem asks us to make three strings s1, s2, and s3 identical by repeatedly deleting their rightmost characters. Each deletion is counted as one operation. The key restriction is that we cannot completely delete a string, so at least one character must remain in each string. If it is impossible to make all three strings equal under these rules, we return -1.

The input consists of three non-empty lowercase strings, each with length between 1 and 100. The output is the minimum number of deletions required to make the strings equal, or -1 if it cannot be done.

Essentially, the problem reduces to finding the longest common prefix among the three strings. Characters at the end of each string beyond this common prefix must be deleted. This gives a direct way to compute the minimum operations.

Important edge cases include:

1. Strings already equal - should return 0.
2. Strings with completely different starting letters - impossible, should return -1.
3. Strings of length 1 - any mismatch makes it impossible.

Approaches

A brute-force approach would simulate deleting characters from the end of each string one by one until the strings match. This would involve checking equality at every combination of truncated strings. While correct, it is inefficient since each string has up to 100 characters, leading to O(n³) comparisons in the worst case.

The optimal approach is based on observing that we only need the longest common prefix of the three strings. Once we find the first position where any of the strings differ, everything beyond that point must be deleted from the longer strings. This reduces the problem to a linear scan of the strings from the start.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Check all truncated combinations until equality found
Optimal	O(n)	O(1)	Find longest common prefix, compute deletions directly

Algorithm Walkthrough

1. Initialize an index pointer i = 0. This will track the current character position in all three strings.
2. Loop while i is less than the length of all three strings and the characters at i in s1, s2, and s3 are equal. Increment i.
3. After the loop, i points to the first character where the strings differ or the end of the shortest string. If i == 0, it means the first characters differ and it is impossible to make the strings equal, so return -1.
4. Calculate the number of deletions needed for each string as the difference between the string length and i. This represents trimming each string to the common prefix.
5. Return the sum of these deletions as the minimum number of operations.

Why it works: By definition, the longest common prefix is the maximal portion of the strings that can remain unchanged. Any character beyond this prefix must be deleted. This guarantees the minimal number of operations because any deletion before this point would require additional steps.

Python Solution

class Solution:
    def findMinimumOperations(self, s1: str, s2: str, s3: str) -> int:
        i = 0
        min_len = min(len(s1), len(s2), len(s3))
        
        while i < min_len and s1[i] == s2[i] == s3[i]:
            i += 1
        
        if i == 0:
            return -1
        
        return (len(s1) - i) + (len(s2) - i) + (len(s3) - i)

The implementation first finds the longest common prefix index i. The while loop ensures that i only advances while all characters at the current index are equal. If no characters match at the start (i == 0), we return -1. Finally, the lengths of the suffixes to delete are summed for all three strings to produce the minimum operations.

Go Solution

func findMinimumOperations(s1 string, s2 string, s3 string) int {
    i := 0
    minLen := len(s1)
    if len(s2) < minLen {
        minLen = len(s2)
    }
    if len(s3) < minLen {
        minLen = len(s3)
    }
    
    for i < minLen && s1[i] == s2[i] && s2[i] == s3[i] {
        i++
    }
    
    if i == 0 {
        return -1
    }
    
    return (len(s1) - i) + (len(s2) - i) + (len(s3) - i)
}

The Go implementation is similar to Python. We compute the minimum length to prevent out-of-bounds errors. The for loop identifies the longest common prefix. The final calculation sums the characters to delete. Go handles strings as byte slices for indexing, so s1[i] is valid.

Worked Examples

Example 1: s1 = "abc", s2 = "abb", s3 = "ab"

Step	i	Common Prefix	Remaining Lengths	Deletions
Initial	0	""	3, 3, 2	0
i=1	1	"a"	2, 2, 1	2
i=2	2	"ab"	1, 1, 0	2

Result: 2 deletions needed.

Example 2: s1 = "dac", s2 = "bac", s3 = "cac"

Step	i	Common Prefix	Deletions
Initial	0	""	-

Since i == 0, return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through characters up to the length of the shortest string
Space	O(1)	Only index variables and lengths are stored

This is efficient because we do not construct new strings or maintain additional data structures.

Test Cases

s = Solution()

# Example cases
assert s.findMinimumOperations("abc", "abb", "ab") == 2  # standard example
assert s.findMinimumOperations("dac", "bac", "cac") == -1  # impossible case

# Boundary cases
assert s.findMinimumOperations("a", "a", "a") == 0  # already equal
assert s.findMinimumOperations("a", "b", "c") == -1  # impossible single characters

# Longer strings with partial match
assert s.findMinimumOperations("abcd", "abce", "abcf") == 3  # delete last 1 from each
assert s.findMinimumOperations("abcde", "abcde", "abcd") == 1  # delete last character from first two

# Edge of maximum length
assert s.findMinimumOperations("a"*100, "a"*99 + "b", "a"*100) == 1  # one deletion from s2

Test	Why
"abc","abb","ab"	Checks normal trimming scenario
"dac","bac","cac"	Ensures impossible case handled
"a","a","a"	Already equal, zero deletions
"a","b","c"	Single-char mismatch handled
"abcd","abce","abcf"	Partial common prefix, correct sum of deletions
"abcde","abcde","abcd"	Different lengths, minimal deletion calculation
Longest strings	Verifies algorithm scales to input limits

Edge Cases

1. No common prefix: If the first characters differ, any attempt to trim will not make strings equal. The implementation correctly returns -1.
2. Strings of different lengths but identical start: The algorithm trims each string to the longest common prefix efficiently by subtracting the prefix length from each string length.
3. Strings of length 1: Special care is required since we cannot delete the only character. The code handles this by returning -1 when the first characters do not match.

This solution handles all the constraints and edge cases efficiently and elegantly.