2937. Make Three Strings Equal
Problem Description
You are provided with three strings, s1
, s2
, and s3
, and you can perform a particular operation on them any number of times. The operation allows you to choose one of these strings and delete its rightmost character, but only if the chosen string is at least 2 characters long. The goal is to determine the fewest number of these operations required to make all three strings identical. If it is impossible to make the three strings equal through any number of operations, the answer should be -1
.
Intuition
When looking for a way to make the three strings equal by deleting characters, we must focus on their commonalities. Since we can only delete characters from the end of a string, the strings could only be made equal if they share a common prefix. The longest common prefix that the strings share will determine the operations. By iterating from the start of the strings and comparing characters at the same index across all three strings, we can identify the length of the common prefix.
If at any position the characters in all three strings do not match, that position marks the maximum limit to which the strings can be made identical. Our operation count will be the total length of all strings minus thrice the length of the identical prefix observed up until the mismatch. If there is no common prefix (e.g., the first characters of the strings do not match), it is impossible to make the strings equal, resulting in -1
. If we reach the end of the shortest string without finding a mismatch, this confirms that the shortest string is the common prefix, and we calculate the number of operations accordingly.
Solution Approach
The solution provided uses a straightforward, brute force approach to determine how we can make the strings equal by trimming them from the right. We do not need any complex data structures or algorithms for this; we rely on basic string manipulation and iteration.
To begin with, we calculate the sum s
of the lengths of the three strings. This sum gives us the total number of characters we have in the strings initially.
We then identify the shortest string length n
by taking the minimum length of the three strings, since the longest possible common prefix cannot exceed the length of the shortest string.
With these initial calculations out of the way, we iterate over each string up to the length of the shortest string (index 0
to n - 1
). On each iteration, we compare the characters of s1
, s2
, and s3
at the current index.
If we find that the characters at index i
are not identical in all three strings, this means that the length of the common prefix is i
. In this case, we calculate the number of operations as s - 3 * i
, which essentially subtracts three times the length of the common prefix (because we would have to delete the remaining characters from each string beyond the common prefix).
But if we find that the first characters themselves do not match (i == 0
), we immediately return -1
since no amount of operations will make the strings equal.
If the loop completes without finding any mismatch, this implies that all strings share a common prefix of length n
. Therefore, we return s - 3 * n
since the total number of operations needed is to delete every character beyond the length of the shortest string, from all three strings.
This approach does not require any special data structures, as it simply involves comparing string characters and basic arithmetic to calculate the required value. The solution is an enumeration strategy that covers all potential cases, ensuring correctness by exhaustively checking each character until the end of the shortest string is reached or a mismatch is encountered.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have three strings:
s1
= "abcde"s2
= "abfg"s3
= "abcef"
Now, we need to apply the solution approach to find out the fewest number of operations required to make all three strings identical:
-
Sum the lengths of
s1
,s2
, ands3
:sum = 5 + 4 + 5 = 14
-
Identify the shortest string length
n
(in this case, it'ss2
with length4
). -
Start iterating from index 0 to index n-1 (0 to 3 in this case) and compare the characters of
s1
,s2
, ands3
at each index. -
Index 0: All strings have 'a' - so continue.
-
Index 1: All strings have 'b' - so continue.
-
Index 2:
s1
has 'c',s2
has 'f', ands3
has 'c'. Here, the characters do not match, so the length of the common prefix is2
. -
Calculate the operation count:
operations = sum - 3 * length_of_prefix = 14 - 3 * 2 = 14 - 6 = 8
.
Thus, we need a minimum of 8 operations to make the strings identical, which means we need to delete the last two characters of s1
and the last two characters of s3
, and then delete all characters of s2
beyond the common prefix "ab".
Solution Implementation
1class Solution:
2 def findMinimumOperations(self, string1: str, string2: str, string3: str) -> int:
3 # Calculate the sum of lengths of all strings
4 total_length = len(string1) + len(string2) + len(string3)
5
6 # Find the minimum length among the three strings
7 minimum_length = min(len(string1), len(string2), len(string3))
8
9 # Iterate over the strings up to the minimum length to check for common prefix
10 for index in range(minimum_length):
11 # If the characters at the current position are different,
12 # there is no common prefix at this index or beyond
13
14 # Check if this is the first character; if so, there's no common prefix at all
15 if not string1[index] == string2[index] == string3[index]:
16 return -1 if index == 0 else total_length - 3 * index
17
18 # If the loop completes, the substrings up to 'minimum_length' are the same
19 # hence, we subtract the length of the common prefix for each string
20 return total_length - 3 * minimum_length
21
1class Solution {
2
3 /**
4 * Find the minimum number of operations to make s1, s2, and s3 not have the same character
5 * at index i where 0 <= i < min(s1.length, s2.length, s3.length)
6 *
7 * @param s1 first string
8 * @param s2 second string
9 * @param s3 third string
10 * @return the minimum number of operations required or -1 if no operation is needed
11 */
12 public int findMinimumOperations(String s1, String s2, String s3) {
13 // Calculate the total length of all strings
14 int totalLength = s1.length() + s2.length() + s3.length();
15 // Find the length of the shortest string
16 int minLength = Math.min(Math.min(s1.length(), s2.length()), s3.length());
17
18 // Iterate over the strings up to the length of the shortest string
19 for (int i = 0; i < minLength; ++i) {
20 // Check if the characters at the current index are not the same
21 if (!(s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i))) {
22 // If it's the first character that is different, return -1 (no operation needed)
23 // Otherwise, return the total number of remaining characters in all strings
24 return i == 0 ? -1 : totalLength - 3 * i;
25 }
26 }
27
28 // If all characters up to the length of the shortest string are the same,
29 // return the total number of remaining characters in all strings
30 return totalLength - 3 * minLength;
31 }
32}
33
1class Solution {
2public:
3 // Function to find the minimum number of operations to make all strings equal
4 // s1, s2, and s3 are the input strings
5 int findMinimumOperations(string s1, string s2, string s3) {
6 // Calculate the sum of lengths of all three strings
7 int total_length = s1.size() + s2.size() + s3.size();
8 // Find the length of the smallest string
9 int smallest_length = min({s1.size(), s2.size(), s3.size()});
10 // Iterate over the range of the smallest string length
11 for (int i = 0; i < smallest_length; ++i) {
12 // Check if the characters at the current index are not equal in all strings
13 if (!(s1[i] == s2[i] && s2[i] == s3[i])) {
14 // If the first characters are not equal, we cannot perform the operation
15 return i == 0 ? -1 : total_length - 3 * i;
16 }
17 }
18 // If all the characters are equal up to the smallest string length, subtract the
19 // corresponding triple count from the total length of all strings
20 return total_length - 3 * smallest_length;
21 }
22};
23
1// Function to find the minimum number of operations to make strings non-overlapping
2function findMinimumOperations(str1: string, str2: string, str3: string): number {
3 // Calculate the sum of the lengths of the strings
4 const totalLength = str1.length + str2.length + str3.length;
5
6 // Find the length of the smallest string
7 const smallestLength = Math.min(str1.length, str2.length, str3.length);
8
9 // Loop through each character up to the length of the smallest string
10 for (let i = 0; i < smallestLength; ++i) {
11 // If at any position the characters of the three strings are not equal
12 if (!(str1[i] === str2[i] && str2[i] === str3[i])) {
13 // If no matching character at beginning, return -1 (no removal possible)
14 return i === 0 ? -1 : totalLength - 3 * i;
15 }
16 }
17
18 // If all characters up to the smallest string's length match, return adjusted totalLength
19 // This is because if all characters match, the overlap is until the end of the smallest string
20 return totalLength - 3 * smallestLength;
21}
22
Time and Space Complexity
The function findMinimumOperations
is a simple loop that executes up to n
iterations, where n
is the minimum length of the input strings s1
, s2
, and s3
. This loop runs only once through the shortest string to check the condition and hence, it operates in linear time with respect to the shortest string length. Therefore, the time complexity is O(n)
.
Regarding the space complexity, the function uses a fixed number of single-value variables (s
and n
) and does not create any data structures that grow with the input size. Thus, the amount of additional memory used is constant, making the space complexity O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!