2800. Shortest String That Contains Three Strings

MediumGreedyStringEnumeration

Problem Description

The problem requires us to construct a string with the shortest possible length that contains three given strings a, b, and c as its substrings. The goal is to not only find the shortest concatenation but also to ensure that if there are multiple such shortest strings, we return the one that comes first lexicographically (i.e., in dictionary order).

A few key points from the problem statement:

A substring is a contiguous sequence of characters within another string.
If two strings differ at some position, the lexicographically smaller one is the string with the character earlier in the alphabet at that position.

Essentially, we are tasked with merging the strings in such a way that they are all present and the resulting string is as short as possible, and among the candidates of equal length, the lexicographically smallest is chosen.

Intuition

The solution relies on finding the best way to overlap the given strings a, b, and c to make the shortest possible string that contains all three.

Here's the intuition behind the solution:

Start by considering all permutations of the given strings because the order in which we concatenate them could affect both the final length and lexicographic order.
To find the best overlap between two strings, we check if one is entirely contained within the other. If so, we can use the longer string as it already encompasses the other.
If neither string contains the other, we look for the longest suffix of one that matches a prefix of the other. This allows us to overlap these parts, reducing the combined length of the concatenated string.
We iterate the process, starting with a pair of strings and then combining the result with the third string.
We keep track of the overall shortest string and update it for each permutation if the new combination is shorter or equal in length but lexicographically smaller.

The key approach is the function f(s, t), which merges strings s and t. It either returns one of the input strings if one contains the other or finds the longest overlap possible to merge them efficiently. We use this function iteratively to combine the permutations of input strings and update our result accordingly.

Using the permutation approach ensures that we consider every possible order of the input strings, while the merging function f ensures that we combine the strings as efficiently as possible for each permutation.

Learn more about Greedy patterns.

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

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Solution Approach

The implementation of the solution uses Python's built-in permutation function from the itertools module to generate all possible orders in which the strings can be concatenated.

Here's the breakdown of the code:

The key part of the implementation is the nested function f(s: str, t: str) which takes two strings s and t, and attempts to merge them.
- It first checks if s is a substring of t or t is a substring of s, and if so, returns the larger string.
- If not, it attempts to find the longest overlap between s and t. It does this by checking the suffix of s against the prefix of t starting from the largest possible overlap and decreasing the size until it finds a match or reaches zero.
- If an overlap is found, it returns the concatenated string excluding the overlapped part in t to avoid duplication.
- If no overlap is found (i reaches 0), it returns the concatenation of s and t.
The solution function minimumString(self, a: str, b: str, c: str) starts with an empty string ans to store the final result.
It then iterates through each permutation of strings a, b, and c, and for each permutation:
- It uses the merge function f to combine the first two strings, and then merges the result with the third string.
- It compares the resulting combined string with the current ans. If ans is empty, or if the new string is shorter, or if it's the same length but lexicographically smaller, ans is updated to this new string.
The algorithm uses iterative comparison and string manipulation to build the most efficient string (shortest and lexicographically smallest) for every permutation of input strings.
Finally, after all permutations are considered and the best merged strings are computed, the function returns the optimal string stored in ans.

By using permutations and a merge function, the algorithm efficiently combines the input strings while always ensuring that the output is the minimum length required to contain all three substrings. It also guarantees that if there are strings of the same minimal length, the lexicographically smallest is chosen.

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

Example Walkthrough

Let's apply the solution approach to a small example with strings a, b, and c. Suppose the given strings are:

a = "abc"
b = "bcx"
c = "cxy"

Following the solution approach:

Step 1: Consider All Permutations

We'll consider all permutations of a, b, and c:

Permutation 1: "abc", "bcx", "cxy"
Permutation 2: "abc", "cxy", "bcx"
Permutation 3: "bcx", "abc", "cxy"
Permutation 4: "bcx", "cxy", "abc"
Permutation 5: "cxy", "abc", "bcx"
Permutation 6: "cxy", "bcx", "abc"

Step 2: Find Best Overlap between Two Strings

Using the function f(s, t) for merging strings, we aim to find the best merge:

Taking the first permutation "abc", "bcx", "cxy" as an example:

Merge "abc" and "bcx" using f: "abc" already contains "bc", so we take the longer string "abcx".
Now merge "abcx" with "cxy": The "cx" part is overlapping, so the result is "abcxy".

Step 3: Iterate the Process for All Other Permutations

Repeat step 2 for all permutations to find the merged string for each.

Step 4: Keep Track of the Overall Shortest and Lexicographically Smallest String

Let’s assume that after computing all permutations, we got another shorter string from a different permutation:

From permutation 4: Merging "bcx" with "cxy" gives "bcxy", and then merging with "abc" gives "abcxy".

In this case, although "abcxy" is not shorter than the one from permutation 1, it is not lexicographically smaller either, so no change is made.

Step 5: Return the Optimal String

After computing all permutations, the shortest string that contains all substrings a, b, and c and is also the first lexicographically is "abcxy".

The optimal string "abcxy" is finally returned as the result.

Solution Implementation

1from itertools import permutations
2
3class Solution:
4    def minimumString(self, string_a: str, string_b: str, string_c: str) -> str:
5        def merge_strings(s1: str, s2: str) -> str:
6            # Check if one string is a subsequence of the other and return the longer one.
7            if s1 in s2:
8                return s2
9            if s2 in s1:
10                return s1
11          
12            # Identify the longest common suffix of s1 and prefix of s2
13            # Then merge s1 and s2 by overlapping this common part
14            len_s1, len_s2 = len(s1), len(s2)
15            for overlap_length in range(min(len_s1, len_s2), 0, -1):
16                if s1[-overlap_length:] == s2[:overlap_length]:
17                    return s1 + s2[overlap_length:]
18          
19            # If there is no overlap, concatenate the strings
20            return s1 + s2
21
22        # Initialize the answer with an empty string.
23        shortest_merged_string = ""
24      
25        # Check all permutations of the input strings to find the shortest merged string
26        for permutation in permutations((string_a, string_b, string_c)):
27            merged_string = merge_strings(merge_strings(permutation[0], permutation[1]), permutation[2])
28            if not shortest_merged_string or len(merged_string) < len(shortest_merged_string) or \
29               (len(merged_string) == len(shortest_merged_string) and merged_string < shortest_merged_string):
30                shortest_merged_string = merged_string
31
32        # Return the shortest string found
33        return shortest_merged_string
34

1class Solution {
2    // Method to find the minimum string composed by overlapping or concatenating a, b, and c
3    public String minimumString(String a, String b, String c) {
4        // Store strings in an array for easy access
5        String[] strings = {a, b, c};
6      
7        // All possible permutations of indices 0, 1, and 2
8        int[][] permutations = {
9            {0, 1, 2}, {0, 2, 1}, 
10            {1, 0, 2}, {1, 2, 0}, 
11            {2, 1, 0}, {2, 0, 1}
12        };
13      
14        // Initialize answer string to be empty at the start
15        String answer = "";
16      
17        // Iterate over all permutations to find the smallest possible overlap string
18        for (int[] perm : permutations) {
19            // Access indices based on the current permutation
20            int i = perm[0], j = perm[1], k = perm[2];
21          
22            // Overlap the first two strings, then overlap the result with the third
23            String temp = overlap(overlap(strings[i], strings[j]), strings[k]);
24          
25            // Check if the current string `temp` is smaller or lexicographically smaller than `answer`
26            if ("".equals(answer) || temp.length() < answer.length()
27                    || (temp.length() == answer.length() && temp.compareTo(answer) < 0)) {
28                answer = temp; // Update `answer` with the new minimum string `temp`
29            }
30        }
31      
32        return answer; // Return the smallest string after all permutations are checked
33    }
34
35    // Helper method to find the overlap between two strings or concatenate if no overlap exists
36    private String overlap(String s, String t) {
37        // If one string contains the other, return the larger string
38        if (s.contains(t)) {
39            return s;
40        }
41        if (t.contains(s)) {
42            return t;
43        }
44
45        int m = s.length(), n = t.length();
46      
47        // Find the maximum overlap starting from the end of `s` and the beginning of `t`
48        for (int i = Math.min(m, n); i > 0; --i) {
49            // If the end of `s` matches the beginning of `t`, concatenate the non-overlapping part
50            if (s.substring(m - i).equals(t.substring(0, i))) {
51                return s + t.substring(i);
52            }
53        }
54      
55        // If there's no overlap, concatenate the strings `s` and `t`
56        return s + t;
57    }
58}
59

1class Solution {
2public:
3    // Function to find the minimum string obtained by concatenating
4    // three input strings in any order without overlapping.
5    string minimumString(string stringA, string stringB, string stringC) {
6        // The input strings are stored in a vector for easy permutation.
7        vector<string> strings = {stringA, stringB, stringC};
8        // All possible permutations of the three strings.
9        vector<vector<int>> permutations = {
10            {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}
11        };
12        // String to store the minimum concatenated result.
13        string minimumResult = "";
14        // Loop over all the permutations.
15        for (auto& permutation : permutations) {
16            // Indices for the permutation
17            int first = permutation[0], second = permutation[1], third = permutation[2];
18            // Concatenate strings based on the current permutation and minimize them.
19            string temp = minimize(strings[first], minimize(strings[second], strings[third]));
20            // Update the minimumResult if a smaller string is found.
21            if (minimumResult.empty() || temp.size() < minimumResult.size() ||
22                (temp.size() == minimumResult.size() && temp < minimumResult)) {
23                minimumResult = temp;
24            }
25        }
26        return minimumResult;
27    }
28
29    // Helper function to minimize two strings by concatenating
30    // without overlapping the maximum number of characters.
31    string minimize(string firstString, string secondString) {
32        // If one string contains the other, return the larger one.
33        if (firstString.find(secondString) != string::npos) {
34            return firstString;
35        }
36        if (secondString.find(firstString) != string::npos) {
37            return secondString;
38        }
39        // Get the lengths of the two strings.
40        int lengthFirst = firstString.size(), lengthSecond = secondString.size();
41        // Try to find the largest overlap starting from the largest possible size.
42        for (int overlapSize = min(lengthFirst, lengthSecond); overlapSize > 0; --overlapSize) {
43            if (firstString.substr(lengthFirst - overlapSize) == secondString.substr(0, overlapSize)) {
44                // If an overlap is found, return the concatenation without the overlapping part.
45                return firstString + secondString.substr(overlapSize);
46            }
47        }
48        // If no overlap is found, return the concatenation of both strings.
49        return firstString + secondString;
50    }
51};
52

1function minimumString(firstString: string, secondString: string, thirdString: string): string {
2    // Function to merge two strings with minimum additional characters
3    const mergeMinimum = (stringA: string, stringB: string): string => {
4        // If one string includes the other, return the longer one
5        if (stringA.includes(stringB)) {
6            return stringA;
7        }
8        if (stringB.includes(stringA)) {
9            return stringB;
10        }
11
12        // Determine the lengths of both strings
13        const lengthA = stringA.length;
14        const lengthB = stringB.length;
15
16        // Find the longest suffix of stringA that is a prefix of stringB
17        for (let overlapLength = Math.min(lengthA, lengthB); overlapLength > 0; --overlapLength) {
18            if (stringA.slice(-overlapLength) === stringB.slice(0, overlapLength)) {
19                // Combine strings without the overlapping part
20                return stringA + stringB.slice(overlapLength);
21            }
22        }
23
24        // If no overlap, return the concatenation of both strings
25        return stringA + stringB;
26    };
27
28    // Declare an array for the input strings
29    const strings: string[] = [firstString, secondString, thirdString];
30
31    // Define all permutations of the indices for string combinations
32    const permutations: number[][] = [
33        [0, 1, 2],
34        [0, 2, 1],
35        [1, 0, 2],
36        [1, 2, 0],
37        [2, 0, 1],
38        [2, 1, 0],
39    ];
40
41    // Initialize the answer string
42    let answer = '';
43
44    // Iterate over each permutation
45    for (const [index1, index2, index3] of permutations) {
46        // Merge the strings according to the current permutation
47        const currentCombo = mergeMinimum(mergeMinimum(strings[index1], strings[index2]), strings[index3]);
48      
49        // Update the answer if the current combination is shorter or lexicographically smaller
50        if (answer === '' || currentCombo.length < answer.length || (currentCombo.length === answer.length && currentCombo < answer)) {
51            answer = currentCombo;
52        }
53    }
54
55    // Return the answer that represents the shortest merged string
56    return answer;
57}
58

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

Time and Space Complexity

Time Complexity

The minimumString function is trying to concatenate three strings a, b, c, in all possible permutations, and find the minimum length string that captures all three original strings possibly overlapping. It uses a nested helper function f, which is applied twice in the worst case, to combine two strings efficiently by checking for overlaps.

There are 6 permutations of (a, b, c), which comes from 3! permutations for three elements.
The helper function f compares every suffix of one string with the prefix of another, this could take up to O(min(m, n)) time where m and n are the lengths of the two strings being merged.
Since f is called twice for each permutation, merging first two and then the result with the third, the cost per permutation is O(m + n) + O(max(m, n, o)), with o being the length of the third string.
Therefore, the total time complexity for the worst case overlaps checking and merging is O(6 * (m + n + max(m, n, o))) which simplifies to O(m + n + o) as constants are dropped in big O notation.

Space Complexity

There is a variable ans which keeps track of the best (shortest) answer found so far. It can take up to O(m + n + o) space in the situation there is no overlap, however since strings are immutable in Python, each concatenation can create a new string, so this will use space proportional to the sum of lengths of a, b, and c.
The function doesn't use any additional data structures which grow with the input size, aside from temporary variables for iteration.
Each call to f creates substrings, which in Python are typically pointers to sections of the original strings and therefore do not consume more space than the original strings.
Hence, the space complexity is O(m + n + o) as well, primarily used by the output string and the input strings.

In conclusion, the time complexity of the given code is O(m + n + o) and the space complexity is also O(m + n + o).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

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

2800. Shortest String That Contains Three Strings

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Consider All Permutations

Step 2: Find Best Overlap between Two Strings

Step 3: Iterate the Process for All Other Permutations

Step 4: Keep Track of the Overall Shortest and Lexicographically Smallest String

Step 5: Return the Optimal String

Solution Implementation