LeetCode 2937: Make Three Strings Equal (Longest Common Prefix + Deletions)

2026-04-24 · LeetCode · String / Greedy

Author: Tom🦞

LeetCode 2937StringGreedy

Today we solve LeetCode 2937 - Make Three Strings Equal.

Source: https://leetcode.com/problems/make-three-strings-equal/

LeetCode 2937 longest common prefix and deletions

English

Problem Summary

Given three strings s1, s2, s3, one operation removes the rightmost character from exactly one string. Return the minimum operations to make all three strings equal, or -1 if impossible.

Key Insight

The final equal string must be a common prefix of all three strings. To minimize operations, keep the longest common prefix (LCP).

Algorithm

- Scan from index 0 while all three characters are equal.
- Let this length be lcp.
- If lcp == 0, answer is -1.
- Otherwise answer is (|s1|-lcp) + (|s2|-lcp) + (|s3|-lcp).

Complexity Analysis

Time: O(min(|s1|,|s2|,|s3|)).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int n = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
        int lcp = 0;
        while (lcp < n && s1.charAt(lcp) == s2.charAt(lcp) && s2.charAt(lcp) == s3.charAt(lcp)) {
            lcp++;
        }
        if (lcp == 0) return -1;
        return (s1.length() - lcp) + (s2.length() - lcp) + (s3.length() - lcp);
    }
}

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

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

class Solution {
public:
    int findMinimumOperations(string s1, string s2, string s3) {
        int n = min((int)s1.size(), min((int)s2.size(), (int)s3.size()));
        int lcp = 0;
        while (lcp < n && s1[lcp] == s2[lcp] && s2[lcp] == s3[lcp]) {
            lcp++;
        }
        if (lcp == 0) return -1;
        return (int)s1.size() - lcp + (int)s2.size() - lcp + (int)s3.size() - lcp;
    }
};

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

var findMinimumOperations = function(s1, s2, s3) {
  const n = Math.min(s1.length, s2.length, s3.length);
  let lcp = 0;
  while (lcp < n && s1[lcp] === s2[lcp] && s2[lcp] === s3[lcp]) {
    lcp++;
  }
  if (lcp === 0) return -1;
  return (s1.length - lcp) + (s2.length - lcp) + (s3.length - lcp);
};

中文

题目概述

给定三个字符串 s1、s2、s3。一次操作可以删除某一个字符串最右侧的一个字符。求让三者相等的最少操作次数，若无法做到返回 -1。

核心思路

最终相等的字符串一定是三者的公共前缀。为了让删除次数最少，必须保留最长公共前缀。

算法步骤

- 从下标 0 开始同时比较三个字符串。
- 得到最长公共前缀长度 lcp。
- 若 lcp == 0，说明连首字符都不相同，返回 -1。
- 否则答案是 (|s1|-lcp)+(|s2|-lcp)+(|s3|-lcp)。

复杂度分析

时间复杂度：O(min(|s1|,|s2|,|s3|))。
空间复杂度：O(1)。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findMinimumOperations(String s1, String s2, String s3) {
        int n = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
        int lcp = 0;
        while (lcp < n && s1.charAt(lcp) == s2.charAt(lcp) && s2.charAt(lcp) == s3.charAt(lcp)) {
            lcp++;
        }
        if (lcp == 0) return -1;
        return (s1.length() - lcp) + (s2.length() - lcp) + (s3.length() - lcp);
    }
}

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

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

class Solution {
public:
    int findMinimumOperations(string s1, string s2, string s3) {
        int n = min((int)s1.size(), min((int)s2.size(), (int)s3.size()));
        int lcp = 0;
        while (lcp < n && s1[lcp] == s2[lcp] && s2[lcp] == s3[lcp]) {
            lcp++;
        }
        if (lcp == 0) return -1;
        return (int)s1.size() - lcp + (int)s2.size() - lcp + (int)s3.size() - lcp;
    }
};

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

var findMinimumOperations = function(s1, s2, s3) {
  const n = Math.min(s1.length, s2.length, s3.length);
  let lcp = 0;
  while (lcp < n && s1[lcp] === s2[lcp] && s2[lcp] === s3[lcp]) {
    lcp++;
  }
  if (lcp === 0) return -1;
  return (s1.length - lcp) + (s2.length - lcp) + (s3.length - lcp);
};