Skip to main content

Greedy

Shortest String That Contains Three Strings Solution In C++/Java/Python/JS

Problem Description

Given three strings a, b, and c, your task is to find a string that has the minimum length and contains all three strings as substrings. If there are multiple such strings, return the lexicographically smallest one.
Return a string denoting the answer to the problem.

Notes:
- A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
-A substring is a contiguous sequence of characters within a string.

Example

Input: a = "abc", b = "bca", c = "aaa"
Output: "aaabca"
Explanation: We show that "aaabca" contains all the given strings: a = ans[2...4], b = ans[3..5], c = ans[0..2]. It can be shown that the length of the resulting string would be at least 6 and "aaabca" is the lexicographically smallest one.

Input: a = "ab", b = "ba", c = "aba"
Output: "aba"
Explanation: We show that the string "aba" contains all the given strings: a = ans[0..1], b = ans[1..2], c = ans[0..2]. Since the length of c is 3, the length of the resulting string would be at least 3. It can be shown that "aba" is the lexicographically smallest one.

Constraints

  • 1 <= a.length, b.length, c.length <= 100
  • a, b, c consist only of lowercase English letters.
šŸ’”
Try it Yourself First
At first glance, this problem feels like merging three strings as tightly as possible while ensuring each appears as a full substring. It hints at finding overlaps between strings and trying all merge orders to minimize length and then choose the smallest lexicographically if tied.

Optimal Approach

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:

  1. 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.
  2. 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.
  3. 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.
  4. We iterate the process, starting with a pair of strings and then combining the result with the third string.
  5. 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.

Approach

Step 1: Prepare All Permutations
There are 3 strings, and their order can be permuted in 3! = 6 ways. Prepare a list of all 6 permutations of their indices.You will try all these 6 permutations to find which order gives the minimum-length final string.

Step 2: Create a minimize(s1, s2) Helper
Write a function that merges two strings with maximum overlap. First, check if one string is already a substring of the other. If yes, return the larger one. If not, try all possible overlaps:

  • Loop from the largest possible overlap (min length of s1 and s2) down to 1.
  • For each overlap size k, check if the suffix of s1 matches the prefix of s2.
  • If it matches, return s1 + remaining part of s2.

If no overlap, simply return s1 + s2.

Step 4: Evaluate Each Permutation
For each of the 6 permutations:

  • Use the minimize() function to merge the second and third strings first.
  • Then merge that result with the first string.
  • This gives you a merged string for the current permutation.

Step 4: Track the Best Result
Maintain a variable to store the minimum merged result.
For each merged result from step 3:

  • If the result is shorter than the current best, update it.
  • If the result is equal in length but lexicographically smaller, update it.

Step 5: Return the Final Answer
After trying all 6 permutations and merging each one, return the shortest lexicographically smallest result found.

Dry Run

Let's do a detailed dry run of the solution on the input: a = "abc", b = "bca", c = "aaa"

Step 1: Prepare All Permutations

There are 6 permutations of the indices [0,1,2] representing [a,b,c]:

  1. [0,1,2] -> (a, b, c)
  2. [0,2,1] -> (a, c, b)
  3. [1,0,2] -> (b, a, c)
  4. [1,2,0] -> (b, c, a)
  5. [2,0,1] -> (c, a, b)
  6. [2,1,0] -> (c, b, a)

We will compute the merged string for each of these permutations.

Step 2: Helper minimize(s1, s2)

This function merges two strings s1 and s2 by overlapping as much as possible.

Step 3: Evaluate Each Permutation

We merge second and third strings, then merge the result with the first string.

Permutation 1: (a, b, c) = ("abc", "bca", "aaa")

  • Merge "bca" and "aaa":
    • Check if one contains the other ā€” no.
    • Try max overlap:
      • Overlap 3: "bca".suffix(3) = "bca", "aaa".prefix(3) = "aaa" ā†’ no match.
      • Overlap 2: "ca" vs "aa" ā†’ no.
      • Overlap 1: "a" vs "a" ā†’ match found!
    • So merged = "bca" + "aa".substr(1) = "bcaaa"
  • Merge "abc" and "bcaaa":
    • Check substring ā€” no.
    • Overlap 3: "abc".suffix(3) = "abc", "bcaaa".prefix(3) = "bca" ā†’ no.
    • Overlap 2: "bc" vs "bc" ā†’ match!
    • So merged = "abc" + "bcaaa".substr(2) = "abcaaa"

Result: "abcaaa"

Permutation 2: (a, c, b) = ("abc", "aaa", "bca")

  • Merge "aaa" and "bca":
    • No substring.
    • Overlap 3: "aaa".suffix(3) = "aaa", "bca".prefix(3) = "bca" ā†’ no.
    • Overlap 2: "aa" vs "bc" ā†’ no.
    • Overlap 1: "a" vs "b" ā†’ no.
    • No overlap ā†’ merged = "aaa" + "bca" = "aaabca"
  • Merge "abc" and "aaabca":
    • Check substring ā€” no.
    • Overlap 3: "abc".suffix(3) = "abc", "aaabca".prefix(3) = "aaa" ā†’ no.
    • Overlap 2: "bc" vs "aa" ā†’ no.
    • Overlap 1: "c" vs "a" ā†’ no.
    • No overlap ā†’ merged = "abc" + "aaabca" = "abcaaabca"

Result: "abcaaabca"

Permutation 3: (b, a, c) = ("bca", "abc", "aaa")

  • Merge "abc" and "aaa":
    • No substring.
    • Overlap 3: "abc".suffix(3) = "abc", "aaa".prefix(3) = "aaa" ā†’ no.
    • Overlap 2: "bc" vs "aa" ā†’ no.
    • Overlap 1: "c" vs "a" ā†’ no.
    • No overlap ā†’ "abcaaa"
  • Merge "bca" and "abcaaa":
    • Check substring ā€” no.
    • Overlap 3: "bca".suffix(3) = "bca", "abcaaa".prefix(3) = "abc" ā†’ no.
    • Overlap 2: "ca" vs "ab" ā†’ no.
    • Overlap 1: "a" vs "a" ā†’ match!
    • Merged = "bca" + "bcaaa".substr(1) = "bcaabcaaa"

Result: "bcaabcaaa"

Permutation 4: (b, c, a) = ("bca", "aaa", "abc")

  • Merge "aaa" and "abc":
    • No substring.
    • Overlap 3: "aaa".suffix(3) = "aaa", "abc".prefix(3) = "abc" ā†’ no.
    • Overlap 2: "aa" vs "ab" ā†’ no.
    • Overlap 1: "a" vs "a" ā†’ match!
    • Merged = "aaa" + "abc".substr(1) = "aaabc"
  • Merge "bca" and "aaabc":
    • Check substring ā€” no.
    • Overlap 3: "bca".suffix(3) = "bca", "aaabc".prefix(3) = "aaa" ā†’ no.
    • Overlap 2: "ca" vs "aa" ā†’ no.
    • Overlap 1: "a" vs "a" ā†’ match!
    • Merged = "bca" + "aabc".substr(1) = "bcaabc"

Result: "bcaabc"

Permutation 5: (c, a, b) = ("aaa", "abc", "bca")

  • Merge "abc" and "bca":
    • No substring.
    • Overlap 3: "abc".suffix(3) = "abc", "bca".prefix(3) = "bca" ā†’ no.
    • Overlap 2: "bc" vs "bc" ā†’ match!
    • Merged = "abc" + "bca".substr(2) = "abca"
  • Merge "aaa" and "abca":
    • Check substring ā€” no.
    • Overlap 3: "aaa".suffix(3) = "aaa", "abca".prefix(3) = "abc" ā†’ no.
    • Overlap 2: "aa" vs "ab" ā†’ no.
    • Overlap 1: "a" vs "a" ā†’ match!
    • Merged = "aaa" + "abca".substr(1) = "aaabca"

Result: "aaabca"

Permutation 6: (c, b, a) = ("aaa", "bca", "abc")

  • Merge "bca" and "abc":
    • No substring.
    • Overlap 3: "bca".suffix(3) = "bca", "abc".prefix(3) = "abc" ā†’ no.
    • Overlap 2: "ca" vs "ab" ā†’ no.
    • Overlap 1: "a" vs "a" ā†’ match!
    • Merged = "bca" + "abc".substr(1) = "bcabc"
  • Merge "aaa" and "bcabc":
    • Check substring ā€” no.
    • Overlap 3: "aaa".suffix(3) = "aaa", "bcabc".prefix(3) = "bca" ā†’ no.
    • Overlap 2: "aa" vs "bc" ā†’ no.
    • Overlap 1: "a" vs "b" ā†’ no.
    • No overlap ā†’ "aaa" + "bcabc" = "aaabcabc"

Result: "aaabcabc"

Step 4: Track the Best Result

  • All merged results and their lengths:

PermutationResultLength(a,b,c)"abcaaa"6(a,c,b)"abcaaabca"9(b,a,c)"bcaabcaaa"9(b,c,a)"bcaabc"6(c,a,b)"aaabca"6(c,b,a)"aaabcabc"8

  • Among length 6 strings: "abcaaa", "bcaabc", "aaabca"
  • Now check lexicographically smallest:
    • "aaabca" < "abcaaa" < "bcaabc"
  • So final answer: "aaabca"

Step 5: Return the final answer

"aaabca" contains all 3 strings as substrings and is the shortest and lex smallest merged string.

Code for All Languages
C++ 
class Solution {
public:

    // Function to find the minimum string obtained by concatenating
    // three input strings in any order without overlapping.
    string minimumString(string stringA, string stringB, string stringC) {
    
        // The input strings are stored in a vector for easy permutation.
        vector<string> strings = {stringA, stringB, stringC};
        
        // All possible permutations of the three strings.
        vector<vector<int>> permutations = {
            {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}
        };
        // String to store the minimum concatenated result.
        string minimumResult = "";
        
        // Loop over all the permutations.
        for (auto& permutation : permutations) {
        
            // Indices for the permutation
            int first = permutation[0], second = permutation[1], third = permutation[2];
            
            // Concatenate strings based on the current permutation and minimize them.
            string temp = minimize(strings[first], minimize(strings[second], strings[third]));
            
            // Update the minimumResult if a smaller string is found.
            if (minimumResult.empty() || temp.size() < minimumResult.size() ||
                (temp.size() == minimumResult.size() && temp < minimumResult)) {
                minimumResult = temp;
            }
        }
        return minimumResult;
    }

    // Helper function to minimize two strings by concatenating
    // without overlapping the maximum number of characters.
    string minimize(string firstString, string secondString) {
    
        // If one string contains the other, return the larger one.
        if (firstString.find(secondString) != string::npos) {
            return firstString;
        }
        if (secondString.find(firstString) != string::npos) {
            return secondString;
        }
        
        // Get the lengths of the two strings.
        int lengthFirst = firstString.size(), lengthSecond = secondString.size();
        
        // Try to find the largest overlap starting from the largest possible size.
        for (int overlapSize = min(lengthFirst, lengthSecond); overlapSize > 0; --overlapSize) {
            if (firstString.substr(lengthFirst - overlapSize) == secondString.substr(0, overlapSize)) {
            
                // If an overlap is found, return the concatenation without the overlapping part.
                return firstString + secondString.substr(overlapSize);
            }
        }
        // If no overlap is found, return the concatenation of both strings.
        return firstString + secondString;
    }
};

Java 
class Solution {
    // Method to find the minimum string composed by overlapping or concatenating a, b, and c
    public String minimumString(String a, String b, String c) {
        // Store strings in an array for easy access
        String[] strings = {a, b, c};
      
        // All possible permutations of indices 0, 1, and 2
        int[][] permutations = {
            {0, 1, 2}, {0, 2, 1}, 
            {1, 0, 2}, {1, 2, 0}, 
            {2, 1, 0}, {2, 0, 1}
        };
      
        // Initialize answer string to be empty at the start
        String answer = "";
      
        // Iterate over all permutations to find the smallest possible overlap string
        for (int[] perm : permutations) {
            // Access indices based on the current permutation
            int i = perm[0], j = perm[1], k = perm[2];
          
            // Overlap the first two strings, then overlap the result with the third
            String temp = overlap(overlap(strings[i], strings[j]), strings[k]);
          
            // Check if the current string `temp` is smaller or lexicographically smaller than `answer`
            if ("".equals(answer) || temp.length() < answer.length()
                    || (temp.length() == answer.length() && temp.compareTo(answer) < 0)) {
                answer = temp; // Update `answer` with the new minimum string `temp`
            }
        }
      
        return answer; // Return the smallest string after all permutations are checked
    }

    // Helper method to find the overlap between two strings or concatenate if no overlap exists
    private String overlap(String s, String t) {
        // If one string contains the other, return the larger string
        if (s.contains(t)) {
            return s;
        }
        if (t.contains(s)) {
            return t;
        }

        int m = s.length(), n = t.length();
      
        // Find the maximum overlap starting from the end of `s` and the beginning of `t`
        for (int i = Math.min(m, n); i > 0; --i) {
            // If the end of `s` matches the beginning of `t`, concatenate the non-overlapping part
            if (s.substring(m - i).equals(t.substring(0, i))) {
                return s + t.substring(i);
            }
        }
      
        // If there's no overlap, concatenate the strings `s` and `t`
        return s + t;
    }
}

Python 
class Solution:
    def minimumString(self, string_a: str, string_b: str, string_c: str) -> str:
        def merge_strings(s1: str, s2: str) -> str:
            # Check if one string is a subsequence of the other and return the longer one.
            if s1 in s2:
                return s2
            if s2 in s1:
                return s1
          
            # Identify the longest common suffix of s1 and prefix of s2
            # Then merge s1 and s2 by overlapping this common part
            len_s1, len_s2 = len(s1), len(s2)
            for overlap_length in range(min(len_s1, len_s2), 0, -1):
                if s1[-overlap_length:] == s2[:overlap_length]:
                    return s1 + s2[overlap_length:]
          
            # If there is no overlap, concatenate the strings
            return s1 + s2

        # Initialize the answer with an empty string.
        shortest_merged_string = ""
      
        # Check all permutations of the input strings to find the shortest merged string
        for permutation in permutations((string_a, string_b, string_c)):
            merged_string = merge_strings(merge_strings(permutation[0], permutation[1]), permutation[2])
            if not shortest_merged_string or len(merged_string) < len(shortest_merged_string) or \
               (len(merged_string) == len(shortest_merged_string) and merged_string < shortest_merged_string):
                shortest_merged_string = merged_string

        # Return the shortest string found
        return shortest_merged_string

Javascript 
var minimumString = function(a, b, c) {
    
    // Helper function to minimize two strings with max overlap
    function minimize(s1, s2) {
        // If s1 contains s2, return s1
        if (s1.includes(s2)) return s1;
        // If s2 contains s1, return s2
        if (s2.includes(s1)) return s2;

        const n1 = s1.length, n2 = s2.length;

        // Try to find the max overlap from back of s1 and front of s2
        for (let k = Math.min(n1, n2); k > 0; --k) {
            if (s1.slice(n1 - k) === s2.slice(0, k)) {
                return s1 + s2.slice(k);
            }
        }

        // No overlap
        return s1 + s2;
    }

    // All permutations of indices for three strings
    const perms = [
        [a, b, c],
        [a, c, b],
        [b, a, c],
        [b, c, a],
        [c, a, b],
        [c, b, a]
    ];

    let minRes = "";

    for (const [x, y, z] of perms) {
        const temp = minimize(x, minimize(y, z));
        if (
            minRes === "" ||
            temp.length < minRes.length ||
            (temp.length === minRes.length && temp < minRes)
        ) {
            minRes = temp;
        }
    }

    return minRes;
};

Time Complexity: O(n^2)

Loop Execution
We consider all 6 permutations of the three input strings,
which is constant (6). For each permutation, we perform two calls to the minimize function, which attempts to merge two strings by checking overlaps. Each minimize(s1, s2) may loop up to n times (where n is the maximum length of the input strings) and compare substrings of up to length n, resulting in O(nĀ²) time per call. So, for two calls per permutation, total time per permutation is O(nĀ²).

Final Time Complexity
Since we check all 6 permutations, the overall time complexity is:
6 Ɨ O(nĀ²) = O(nĀ²)
Thus, the final time complexity is O(nĀ²).

Space Complexity: O(1)

Auxiliary Space Complexity:
This refers to any extra space used by the algorithm that is independent of the input space and output space. In this case, we only use a constant amount of extra space ā€” specifically for storing the temporary result strings, loop variables, and fixed permutations. These variables do not depend on the size of the input strings and therefore take up constant space. So, the auxiliary space complexity is O(1).

Total Space Complexity:
This includes the space required for the input, output, and extra space used by the algorithm as well. The input strings a, b, and c are of size up to n, so the input space is O(n). The output string can also be of size up to 3n in the worst case (if there is no overlap), which is still O(n). The algorithm only uses constant auxiliary space for computation.
Total Space Complexity = O(n) + O(n) + O(1) = O(n)

Thus, the total space complexity is O(n).

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Largest Merge Of Two Strings

Given two strings word1 and word2, construct the lexicographically largest string merge by repeatedly choosing the first character from either string. Always pick from the string whose remaining portion is lexicographically greater.