Make Three Strings Equal solution and explanation
9 more videos on this problem
2937. Make Three Strings Equal || Prefix Check 🔥|| Greedy 🔥Ayush Rao · 6:29 · 598 views
Make Three Strings Equal - Leetcode 2937 - PythonCheatCode Ninja · 5:04 · 376 views
2937. Make Three Strings Equal | Contest 372Tech Courses · 5:58 · 368 views
Leetcode 2937 Make Three Strings EqualLuc Taylor · 5:29 · 349 views
2937. Make Three Strings Equal (Leetcode Easy)Programming Live with Larry · 8:19 · 238 views
Make Three Strings Equal - LeetCode 2937 - PythonAlpha-Code · 8:17 · 110 views
2937. Make Three Strings Equal #leetcodequestionandanswers #java #coding #stringsCodeVia · 3:28 · 105 views
#LeetCode 2937 | Make Three Strings Equal #JavaSleepy Cracker · 4:23 · 59 views
Day 670: LeetCode Problem 2937. Make Three Strings Equal - SwiftiOSxBank · 8:24 · 47 views
2937. Make Three Strings EqualRounaq Khandelwal · 5:25 · 46 views
The problem
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 <= 100s1,s2ands3consist only of lowercase English letters.
Approach overview
Problem Overview: You are given three strings and can only delete characters from the end of any string. The goal is to make all three strings exactly equal using the minimum number of deletions. If no common string can remain after deletions, return -1.
Approach 1: Common Prefix with Trimming (O(n) time, O(1) space)
Deleting characters only from the end means the final result must be a prefix shared by all three strings. The problem reduces to finding the longest common prefix among the three strings. Iterate character by character while all three strings match at the same index. Stop when a mismatch appears or one string ends. If the longest common prefix length is k, each string must be trimmed to length k, so the total operations equal (len(s1) - k) + (len(s2) - k) + (len(s3) - k). This scan takes linear time proportional to the smallest string length, making it an efficient string traversal problem.
Approach 2: Longest Common Suffix via Reverse Scan (O(n) time, O(1) space)
Another way to reason about the constraint is from the opposite direction. Since deletions happen from the right side, you can repeatedly trim the longest string until all three strings become identical. A practical implementation reverses the strings and computes their longest common suffix (which corresponds to the prefix of the original strings). Iterate with two pointers across the reversed strings and stop when characters differ. The length of this shared suffix determines how many characters can remain in each string. The remaining characters must be deleted. This approach still performs a single linear scan and uses constant extra memory, relying only on simple character comparisons and basic string operations.
Recommended for interviews: The Common Prefix with Trimming approach is what most interviewers expect. It directly models the constraint that deletions happen at the end and leads naturally to the longest common prefix observation. The suffix/reverse method shows the same insight from another perspective and demonstrates strong reasoning about string manipulation. Both achieve optimal O(n) time with O(1) space.
Approach 1: Longest Common Suffix Approach
To make all three strings equal, we need to effectively align their tails. A valid equalization would require the remaining parts of each string to be the same, forming a common suffix. We can iterate over the strings from the end towards the beginning and find the longest suffix that is common to all three. The answer will be the total length of the original strings minus three times the length of this common suffix.
def minOperationsToEqualize(s1, s2, s3):
suffix_len = 0
while (suffix_len < len(s1) and suffix_len < len(s2) and suffix_len < len(s3) and
s1[-suffix_len-1] == s2[-suffix_len-1] == s3[-suffix_len-1]):
suffix_len += 1
min_operations = len(s1) + len(s2) + len(s3) - 3 * suffix_len
return -1 if suffix_len == 0 else min_operations
print(minOperationsToEqualize("abc", "abb", "ab"))public class Main {
public static int minOperationsToEqualize(String s1, String s2, String s3) {
int suffixLen = 0;
while (suffixLen < s1.length() && suffixLen < s2.length() && suffixLen < s3.length() &&
s1.charAt(s1.length() - suffixLen - 1) == s2.charAt(s2.length() - suffixLen - 1) &&
s2.charAt(s2.length() - suffixLen - 1) == s3.charAt(s3.length() - suffixLen - 1)) {
suffixLen++;
}
int minOperations = s1.length() + s2.length() + s3.length() - 3 * suffixLen;
return (suffixLen == 0) ? -1 : minOperations;
}
public static void main(String[] args) {
System.out.println(minOperationsToEqualize("abc", "abb", "ab"));
}
}#include <iostream>
#include <string>
int minOperationsToEqualize(const std::string& s1, const std::string& s2, const std::string& s3) {
int suffixLen = 0;
while (suffixLen < s1.size() && suffixLen < s2.size() && suffixLen < s3.size() &&
s1[s1.size() - suffixLen - 1] == s2[s2.size() - suffixLen - 1] &&
s2[s2.size() - suffixLen - 1] == s3[s3.size() - suffixLen - 1]) {
suffixLen++;
}
int minOperations = s1.size() + s2.size() + s3.size() - 3 * suffixLen;
return (suffixLen == 0) ? -1 : minOperations;
}
int main() {
std::string s1 = "abc", s2 = "abb", s3 = "ab";
std::cout << minOperationsToEqualize(s1, s2, s3) << std::endl;
return 0;
}function minOperationsToEqualize(s1, s2, s3) {
let suffixLen = 0;
while (suffixLen < s1.length && suffixLen < s2.length && suffixLen < s3.length &&
s1[s1.length - suffixLen - 1] === s2[s2.length - suffixLen - 1] &&
s2[s2.length - suffixLen - 1] === s3[s3.length - suffixLen - 1]) {
suffixLen++;
}
let minOperations = s1.length + s2.length + s3.length - 3 * suffixLen;
return (suffixLen === 0) ? -1 : minOperations;
}
console.log(minOperationsToEqualize("abc", "abb", "ab"));#include <stdio.h>
#include <string.h>
int minOperationsToEqualize(char *s1, char *s2, char *s3) {
int len1 = strlen(s1), len2 = strlen(s2), len3 = strlen(s3);
int suffixLen = 0;
while (len1 > suffixLen && len2 > suffixLen && len3 > suffixLen &&
s1[len1 - suffixLen - 1] == s2[len2 - suffixLen - 1] && s2[len2 - suffixLen - 1] == s3[len3 - suffixLen - 1]) {
suffixLen++;
}
int minOperations = len1 + len2 + len3 - 3 * suffixLen;
return (suffixLen == 0) ? -1 : minOperations;
}
int main() {
char s1[] = "abc";
char s2[] = "abb";
char s3[] = "ab";
printf("%d\n", minOperationsToEqualize(s1, s2, s3));
return 0;
}using System;
class Program {
static int MinOperationsToEqualize(string s1, string s2, string s3) {
int suffixLen = 0;
while (suffixLen < s1.Length && suffixLen < s2.Length && suffixLen < s3.Length &&
s1[s1.Length - suffixLen - 1] == s2[s2.Length - suffixLen - 1] &&
s2[s2.Length - suffixLen - 1] == s3[s3.Length - suffixLen - 1]) {
suffixLen++;
}
int minOperations = s1.Length + s2.Length + s3.Length - 3 * suffixLen;
return (suffixLen == 0) ? -1 : minOperations;
}
static void Main() {
Console.WriteLine(MinOperationsToEqualize("abc", "abb", "ab"));
}
}This Python solution efficiently computes the longest common suffix by iterating in reverse order. It calculates the minimum number of deletions needed once the longest common suffix is determined.
Time Complexity: O(n) due to linear traversal of the strings. Space Complexity: O(1) with constant extra space usage.
Approach 2: Common Prefix with Trimming
This approach involves trimming the strings by checking common prefixes instead of suffixes. The idea is to keep trimming the strings from the start until a common prefix forms among them, and the answer will be the total operations needed to reach one common prefix.
def minOperationsByPrefix(s1, s2, s3):
prefix_len = 0
while (prefix_len < len(s1) and prefix_len < len(s2) and prefix_len < len(s3) and
s1[prefix_len] == s2[prefix_len] == s3[prefix_len]):
prefix_len += 1
if prefix_len == 0:
return -1
return len(s1) + len(s2) + len(s3) - 3 * prefix_len
print(minOperationsByPrefix("abc", "abb", "ab"))public class Main {
public static int minOperationsByPrefix(String s1, String s2, String s3) {
int prefixLen = 0;
while (prefixLen < s1.length() && prefixLen < s2.length() && prefixLen < s3.length() &&
s1.charAt(prefixLen) == s2.charAt(prefixLen) && s2.charAt(prefixLen) == s3.charAt(prefixLen)) {
prefixLen++;
}
if (prefixLen == 0) return -1;
return s1.length() + s2.length() + s3.length() - 3 * prefixLen;
}
public static void main(String[] args) {
System.out.println(minOperationsByPrefix("abc", "abb", "ab"));
}
}#include <iostream>
#include <string>
int minOperationsByPrefix(const std::string& s1, const std::string& s2, const std::string& s3) {
int prefixLen = 0;
while (prefixLen < s1.length() && prefixLen < s2.length() && prefixLen < s3.length() &&
s1[prefixLen] == s2[prefixLen] && s2[prefixLen] == s3[prefixLen]) {
prefixLen++;
}
if (prefixLen == 0) return -1;
return s1.length() + s2.length() + s3.length() - 3 * prefixLen;
}
int main() {
std::string s1 = "abc", s2 = "abb", s3 = "ab";
std::cout << minOperationsByPrefix(s1, s2, s3) << std::endl;
return 0;
}function minOperationsByPrefix(s1, s2, s3) {
let prefixLen = 0;
while (prefixLen < s1.length && prefixLen < s2.length && prefixLen < s3.length &&
s1[prefixLen] === s2[prefixLen] && s2[prefixLen] === s3[prefixLen]) {
prefixLen++;
}
if (prefixLen === 0) return -1;
return s1.length + s2.length + s3.length - 3 * prefixLen;
}
console.log(minOperationsByPrefix("abc", "abb", "ab"));#include <stdio.h>
#include <string.h>
int minOperationsByPrefix(char *s1, char *s2, char *s3) {
int prefixLen = 0;
while (prefixLen < strlen(s1) && prefixLen < strlen(s2) && prefixLen < strlen(s3) &&
s1[prefixLen] == s2[prefixLen] && s2[prefixLen] == s3[prefixLen]) {
prefixLen++;
}
if (prefixLen == 0) return -1;
return strchr(s1, '\0') - s1 + strchr(s2, '\0') - s2 + strchr(s3, '\0') - s3 - 3 * prefixLen;
}
int main() {
char s1[] = "abc";
char s2[] = "abb";
char s3[] = "ab";
printf("%d\n", minOperationsByPrefix(s1, s2, s3));
return 0;
}using System;
class Program {
static int MinOperationsByPrefix(string s1, string s2, string s3) {
int prefixLen = 0;
while (prefixLen < s1.Length && prefixLen < s2.Length && prefixLen < s3.Length &&
s1[prefixLen] == s2[prefixLen] && s2[prefixLen] == s3[prefixLen]) {
prefixLen++;
}
if (prefixLen == 0) return -1;
return s1.Length + s2.Length + s3.Length - 3 * prefixLen;
}
static void Main() {
Console.WriteLine(MinOperationsByPrefix("abc", "abb", "ab"));
}
}A Python method that employs a loop to check prefixes and calculates required deletions once the common prefix is determined by measuring the mismatch position forward.
Time Complexity: O(n), Space Complexity: O(1).
Approach 3: Enumeration
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).
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Longest Common Suffix Approach | Time Complexity: O(n) due to linear traversal of the strings. Space Complexity: O(1) with constant extra space usage. |
| Common Prefix with Trimming | Time Complexity: O(n), Space Complexity: O(1). |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Common Prefix with Trimming | O(n) | O(1) | Best general solution. Directly models the constraint that only suffix characters can be removed. |
| Longest Common Suffix (Reverse Scan) | O(n) | O(1) | Useful when reasoning from the deletion direction or when implementing reverse string comparisons. |
Frequently asked questions
Is Make Three Strings Equal easy or hard?
Make Three Strings Equal is classified as an Easy problem. The key insight is recognizing that deleting from the end forces the final result to be a common prefix. Once that observation is made, the implementation becomes a straightforward linear scan.
Make Three Strings Equal Python/Java solution
In Python or Java, iterate with an index while characters match across all three strings. Stop when a mismatch occurs or one string ends. Calculate the remaining characters in each string and sum them to get the number of deletions. The implementation is short and runs in O(n) time.
How to solve Make Three Strings Equal in O(n)?
Iterate through the three strings simultaneously and determine the longest common prefix length k. Once a mismatch appears, stop the scan. The number of deletions required is (len(s1) - k) + (len(s2) - k) + (len(s3) - k). This single pass ensures linear time complexity.
What is the best approach for Make Three Strings Equal?
The best approach is finding the longest common prefix among the three strings. Since deletions are allowed only from the end, the final equal string must be a shared prefix. Scan all three strings simultaneously until characters differ, then compute the number of deletions needed. This runs in O(n) time and O(1) space.
Is Make Three Strings Equal asked at Google/Amazon/Meta?
Problems based on longest common prefix and constrained string deletions appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary in wording, the underlying pattern—prefix comparison and greedy trimming—is a common string interview concept.
What data structure is used in Make Three Strings Equal?
The problem mainly uses basic string traversal with index pointers. No advanced data structures are required. The solution relies on comparing characters across multiple strings and computing prefix lengths.
What is the time complexity of Make Three Strings Equal?
The optimal solution runs in O(n) time where n is the length of the shortest string. The algorithm compares characters across the three strings once to find their longest common prefix. Space complexity remains O(1) because only counters and indices are used.