Jobs

Interviews

Discussions

Make Three Strings Equal

Easy

Asked by:

3 views

Topics:

Strings

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.

Try coding it in LeetCode

Make Three Strings Equal

Easy

Asked by:

3 views

Topics:

Strings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings be empty or null?
What are the maximum lengths of the input strings?
Are the strings case-sensitive?
If there is no common prefix among all three strings, what should the function return?
By 'equal', do you mean that the strings need to have identical character sequences, or is there any tolerance for minor variations?

Brute Force Solution

Approach

The goal is to find the longest common prefix among three strings by checking all possible prefixes. We will explore increasingly longer prefixes, one character at a time. This involves comparing these prefixes across all three strings.

Here's how the algorithm would work step-by-step:

Start by looking at the first character of each string.
See if the first character is the same across all three strings.
If they're all the same, then this single character is a potential prefix.
Next, look at the first two characters of each string.
Check if these two-character sequences are the same in all three strings.
If they match, this two-character sequence is a longer potential prefix.
Continue this process, adding one more character at a time to the prefix and comparing it across all strings.
Stop when you find a length where the prefixes no longer match in all three strings or you reach the end of the shortest string.
The longest prefix that matched before you hit the mismatch or the end is the answer.

Code Implementation

def find_longest_prefix(first_string, second_string, third_string):
    shortest_string_length = min(len(first_string), len(second_string), len(third_string))
    longest_common_prefix = ''

    for prefix_length in range(1, shortest_string_length + 1):
        # Extract the prefix of the current length from each string
        first_string_prefix = first_string[:prefix_length]

        second_string_prefix = second_string[:prefix_length]

        third_string_prefix = third_string[:prefix_length]

        # Check if all prefixes are equal
        if first_string_prefix == second_string_prefix and second_string_prefix == third_string_prefix:
            # Update the longest common prefix if match is found
            longest_common_prefix = first_string_prefix
        else:
            # Stop if the prefixes are not the same
            break

    # The longest prefix that matched is the answer
    return longest_common_prefix

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the characters of the strings, extending the prefix by one character in each iteration. In the worst case, the algorithm iterates up to the length of the shortest string. The comparison of prefixes in each iteration takes constant time. Therefore, the time complexity is directly proportional to the length of the shortest string, which we can denote as n. Thus, the overall time complexity is O(n).

Space Complexity

O(1) – The described algorithm iteratively compares prefixes of the input strings character by character. It doesn't create any auxiliary data structures like lists, arrays, or hash maps to store intermediate results or track visited prefixes. The space used is limited to storing a few index variables for tracking the prefix length during comparisons, which is independent of the input string lengths. Therefore, the space complexity is constant.

Optimal Solution

Approach

To make the three strings equal with the fewest steps, find the longest common part they share at the beginning. Then, remove the different parts from the end of each string to leave only that common part.

Here's how the algorithm would work step-by-step:

Compare the characters of all three strings, starting from the beginning.
Find the point where the strings start to have different characters.
The part of the strings before this difference is the longest common prefix.
Remove the different characters from the end of each of the original strings, until you are left with just the common prefix for each string.
The resulting strings will be equal, and you've done it in the fewest steps by maximizing the shared part and minimizing removals.

Code Implementation

def make_three_strings_equal(first_string, second_string, third_string):
    minimum_length = min(len(first_string), len(second_string), len(third_string))
    common_prefix_length = 0

    # Find the length of the longest common prefix.
    for i in range(minimum_length):
        if first_string[i] == second_string[i] == third_string[i]:
            common_prefix_length += 1
        else:
            break

    # If no common prefix exists, no characters can remain.
    if common_prefix_length == 0:
        return 0

    # Calculate the number of characters to remove from each string.
    removal_count = (len(first_string) - common_prefix_length) + \
                    (len(second_string) - common_prefix_length) + \
                    (len(third_string) - common_prefix_length)

    return removal_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the characters of the strings to find the longest common prefix. In the worst case, it might need to iterate through the shortest string completely, where n represents the length of the shortest string. After finding the common prefix, the algorithm truncates the strings, which takes constant time for each string. Therefore, the overall time complexity is determined by the search for the common prefix, making it O(n).

Space Complexity

O(1) – The provided steps focus on comparing characters and finding a common prefix without using any auxiliary data structures that scale with the input string lengths. No extra lists, hash maps, or other data structures are mentioned. The operations involve comparing and potentially modifying the original strings (though the space complexity focuses on auxiliary space, and in-place modification doesn't contribute to auxiliary space), suggesting a constant amount of extra memory is used regardless of the input string sizes. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
One or more strings are null or empty	Return 0 immediately as no common prefix can exist with an empty string.
All three strings are identical	Return the length of any string (they're all the same).
Strings have vastly different lengths (e.g., one is length 1, another is length 1000)	The algorithm should iterate only up to the length of the shortest string to avoid out-of-bounds errors.
No common prefix exists between any of the strings	Return 0, indicating no characters can be removed.
The common prefix is very long, potentially close to the maximum allowed string length	Ensure the string comparison and length calculation do not cause integer overflow or memory issues.
Strings contain non-ASCII characters or Unicode characters	Ensure the character comparison uses the correct encoding and handles multi-byte characters correctly.
Strings consist entirely of whitespace characters	The algorithm should treat whitespace characters like any other character during prefix comparison.
Two strings share a longer prefix than all three do	The algorithm must correctly identify the longest common prefix shared by all three strings, not just a pair.

One or more strings are null or empty

How to Handle:

Return 0 immediately as no common prefix can exist with an empty string.

All three strings are identical

How to Handle:

Return the length of any string (they're all the same).

Strings have vastly different lengths (e.g., one is length 1, another is length 1000)

How to Handle:

The algorithm should iterate only up to the length of the shortest string to avoid out-of-bounds errors.

No common prefix exists between any of the strings

How to Handle:

Return 0, indicating no characters can be removed.

The common prefix is very long, potentially close to the maximum allowed string length

How to Handle:

Ensure the string comparison and length calculation do not cause integer overflow or memory issues.

Strings contain non-ASCII characters or Unicode characters

How to Handle:

Ensure the character comparison uses the correct encoding and handles multi-byte characters correctly.

Strings consist entirely of whitespace characters

How to Handle:

The algorithm should treat whitespace characters like any other character during prefix comparison.

Two strings share a longer prefix than all three do

How to Handle:

The algorithm must correctly identify the longest common prefix shared by *all three* strings, not just a pair.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings be empty or null?
What are the maximum lengths of the input strings?
Are the strings case-sensitive?
If there is no common prefix among all three strings, what should the function return?
By 'equal', do you mean that the strings need to have identical character sequences, or is there any tolerance for minor variations?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first character of each string.
See if the first character is the same across all three strings.
If they're all the same, then this single character is a potential prefix.
Next, look at the first two characters of each string.
Check if these two-character sequences are the same in all three strings.
If they match, this two-character sequence is a longer potential prefix.
Continue this process, adding one more character at a time to the prefix and comparing it across all strings.
Stop when you find a length where the prefixes no longer match in all three strings or you reach the end of the shortest string.
The longest prefix that matched before you hit the mismatch or the end is the answer.

Code Implementation

def find_longest_prefix(first_string, second_string, third_string):
    shortest_string_length = min(len(first_string), len(second_string), len(third_string))
    longest_common_prefix = ''

    for prefix_length in range(1, shortest_string_length + 1):
        # Extract the prefix of the current length from each string
        first_string_prefix = first_string[:prefix_length]

        second_string_prefix = second_string[:prefix_length]

        third_string_prefix = third_string[:prefix_length]

        # Check if all prefixes are equal
        if first_string_prefix == second_string_prefix and second_string_prefix == third_string_prefix:
            # Update the longest common prefix if match is found
            longest_common_prefix = first_string_prefix
        else:
            # Stop if the prefixes are not the same
            break

    # The longest prefix that matched is the answer
    return longest_common_prefix

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Compare the characters of all three strings, starting from the beginning.
Find the point where the strings start to have different characters.
The part of the strings before this difference is the longest common prefix.
Remove the different characters from the end of each of the original strings, until you are left with just the common prefix for each string.
The resulting strings will be equal, and you've done it in the fewest steps by maximizing the shared part and minimizing removals.

Code Implementation

def make_three_strings_equal(first_string, second_string, third_string):
    minimum_length = min(len(first_string), len(second_string), len(third_string))
    common_prefix_length = 0

    # Find the length of the longest common prefix.
    for i in range(minimum_length):
        if first_string[i] == second_string[i] == third_string[i]:
            common_prefix_length += 1
        else:
            break

    # If no common prefix exists, no characters can remain.
    if common_prefix_length == 0:
        return 0

    # Calculate the number of characters to remove from each string.
    removal_count = (len(first_string) - common_prefix_length) + \
                    (len(second_string) - common_prefix_length) + \
                    (len(third_string) - common_prefix_length)

    return removal_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
One or more strings are null or empty	Return 0 immediately as no common prefix can exist with an empty string.
All three strings are identical	Return the length of any string (they're all the same).
Strings have vastly different lengths (e.g., one is length 1, another is length 1000)	The algorithm should iterate only up to the length of the shortest string to avoid out-of-bounds errors.
No common prefix exists between any of the strings	Return 0, indicating no characters can be removed.
The common prefix is very long, potentially close to the maximum allowed string length	Ensure the string comparison and length calculation do not cause integer overflow or memory issues.
Strings contain non-ASCII characters or Unicode characters	Ensure the character comparison uses the correct encoding and handles multi-byte characters correctly.
Strings consist entirely of whitespace characters	The algorithm should treat whitespace characters like any other character during prefix comparison.
Two strings share a longer prefix than all three do	The algorithm must correctly identify the longest common prefix shared by all three strings, not just a pair.

One or more strings are null or empty

How to Handle:

Return 0 immediately as no common prefix can exist with an empty string.

All three strings are identical

How to Handle:

Return the length of any string (they're all the same).

Strings have vastly different lengths (e.g., one is length 1, another is length 1000)

How to Handle:

The algorithm should iterate only up to the length of the shortest string to avoid out-of-bounds errors.

No common prefix exists between any of the strings

How to Handle:

Return 0, indicating no characters can be removed.

The common prefix is very long, potentially close to the maximum allowed string length

How to Handle:

Ensure the string comparison and length calculation do not cause integer overflow or memory issues.

Strings contain non-ASCII characters or Unicode characters

How to Handle:

Ensure the character comparison uses the correct encoding and handles multi-byte characters correctly.

Strings consist entirely of whitespace characters

How to Handle:

The algorithm should treat whitespace characters like any other character during prefix comparison.

Two strings share a longer prefix than all three do

How to Handle:

The algorithm must correctly identify the longest common prefix shared by *all three* strings, not just a pair.