Leetcode 2937: Make Three Strings Equal

Input: You are given three strings, s1, s2, and s3.

Example: s1 = 'hello', s2 = 'heco', s3 = 'heo'

Constraints:

• 1 <= s1.length, s2.length, s3.length <= 100

• s1, s2, and s3 consist only of lowercase English letters.

Output: Return the minimum number of operations required to make all strings equal, or -1 if it is impossible.

Example: For s1 = 'hello', s2 = 'heco', s3 = 'heo', the output is 2.

Constraints:

Goal: The goal is to find the minimum number of operations to make the strings identical by removing the rightmost character from one of the strings in each operation.

Steps:

• Start by comparing the longest common prefix among the three strings.

• For each common prefix, calculate how many characters need to be removed from each string to make them equal to the prefix.

• Return the smallest number of operations or -1 if no common prefix exists.

Goal: The strings are non-empty and consist of lowercase English letters.

Steps:

• 1 <= s1.length, s2.length, s3.length <= 100

• s1, s2, and s3 consist only of lowercase English letters.

Assumptions:

• The strings contain only lowercase English letters.

• Strings will not be empty.

• Input: s1 = 'hello', s2 = 'heco', s3 = 'heo'

• Explanation: By removing the rightmost character from both s1 and s2, all three strings become 'he'. Therefore, it takes 2 operations to make them equal.

• Input: s1 = 'cat', s2 = 'dog', s3 = 'bat'

• Explanation: The strings cannot be made equal because the first characters are different, so the answer is -1.

Approach: The approach is to find the longest common prefix of all three strings and calculate the minimum number of deletions required to make the strings equal.

Observations:

• The problem boils down to finding the longest common prefix.

• If the longest common prefix is of length k, the number of operations required will be the length of each string minus k.

Steps:

• Compare the strings character by character from the beginning until a mismatch is found.

• For each valid prefix, calculate how many characters need to be deleted from each string to make them equal.

• Return the result with the minimum number of deletions.

Empty Inputs:

• If any of the strings is empty, return -1 as it is impossible to make them equal.

Large Inputs:

• The solution should work for strings of length up to 100.

Special Values:

• If all strings are already equal, no operations are needed.

Constraints:

• The strings must not be empty.

int findMinimumOperations(string s1, string s2, string s3) {
    int l1=s1.length(), l2=s2.length(), l3=s3.length();
		int len=min({l1,l2,l3});
    
    int ans=INT_MAX;
    for(int i=0;i<len;i++){
        if(s1.substr(0,i+1) == s2.substr(0,i+1) && s2.substr(0,i+1) == s3.substr(0,i+1)){
            int c=l1-(i+1)+l2-(i+1)+l3-(i+1);
            ans=min(ans,c);
        }
    }
    
    return (ans==INT_MAX ? -1:ans);
}

1 : Function Definition

int findMinimumOperations(string s1, string s2, string s3) {

Defines the function 'findMinimumOperations' that takes three strings as input and returns the minimum number of deletions required to make all three strings equal, or -1 if it's not possible.

2 : Length Calculation

    int l1=s1.length(), l2=s2.length(), l3=s3.length();

Calculates the lengths of the three input strings, s1, s2, and s3, and stores them in l1, l2, and l3 respectively.

3 : Minimum Length Calculation

		int len=min({l1,l2,l3});

Finds the minimum length of the three strings to limit the loop iteration to the shortest string.

4 : Answer Initialization

    int ans=INT_MAX;

Initializes the variable 'ans' to the maximum integer value, representing the minimum number of deletions, which will be updated during the loop.

5 : Loop Setup

    for(int i=0;i<len;i++){

Sets up a loop to iterate through the characters of the strings up to the length of the shortest string.

6 : Substring Comparison

        if(s1.substr(0,i+1) == s2.substr(0,i+1) && s2.substr(0,i+1) == s3.substr(0,i+1)){

Compares the substrings of s1, s2, and s3 from the beginning up to index i. If all three substrings match, the code inside the if block is executed.

7 : Operation Count Calculation

            int c=l1-(i+1)+l2-(i+1)+l3-(i+1);

Calculates the number of deletions required to make the substrings match by subtracting (i+1) from the length of each string and summing them.

8 : Answer Update

            ans=min(ans,c);

Updates the answer with the minimum value between the current answer and the calculated deletions.

9 : Final Answer

    return (ans==INT_MAX ? -1:ans);

Returns the minimum number of deletions needed, or -1 if no such operation was found.

Best Case: O(min(s1.length, s2.length, s3.length))

Average Case: O(min(s1.length, s2.length, s3.length))

Worst Case: O(min(s1.length, s2.length, s3.length))

Description: The complexity is dominated by the comparison of the strings.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant as we only need a few variables to store intermediate results.

Leetcode 2937: Make Three Strings Equal

Explore →