2937. Make Three Strings Equal

EasyString

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example 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, and s3: sum = 5 + 4 + 5 = 14
Identify the shortest string length n (in this case, it's s2 with length 4).
Start iterating from index 0 to index n-1 (0 to 3 in this case) and compare the characters of s1, s2, and s3 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', and s3 has 'c'. Here, the characters do not match, so the length of the common prefix is 2.
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

Not Sure What to Study? Take the 2-min Quiz：

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.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayMerge sort does not use divide and conquer

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2937. Make Three Strings Equal

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings