LeetCode 2800: Shortest String That Contains Three Strings Solution

Master LeetCode problem 2800 (Shortest String That Contains Three Strings), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2800. Shortest String That Contains Three Strings

Medium

String Greedy Enumeration

Problem Explanation

Explanation

To find the shortest string that contains three given strings as substrings, we can concatenate the strings in different orders and then find the lexicographically smallest one. We can generate all possible permutations of the three strings, find the shortest one that contains all three strings, and return it.

Generate all permutations of the three strings.
For each permutation, concatenate the strings in that order.
Keep track of the shortest string that contains all three substrings.
Return the lexicographically smallest shortest string.

Time Complexity:

Generating all permutations has a time complexity of O(3!) = O(6). Concatenating the strings has a time complexity of O(n), where n is the sum of the lengths of the three strings. So, the overall time complexity is O(6 * n) = O(n).

Space Complexity:

The space complexity for storing all permutations is O(3!) = O(6). The space complexity for storing the result is O(n). Hence, the overall space complexity is O(6 + n) = O(n).

Solution Code

class Solution {
    public String shortestString(String a, String b, String c) {
        String[] strs = new String[] {a, b, c};
        String shortest = null;

        // Generate all permutations of the three strings
        List<String> permutations = new ArrayList<>();
        generatePermutations(strs, 0, permutations);

        for (String perm : permutations) {
            // Concatenate the strings in the order of the permutation
            StringBuilder sb = new StringBuilder();
            for (char ch : perm.toCharArray()) {
                sb.append(strs[ch - '0']);
            }

            // Check if the concatenated string contains all three substrings
            if (sb.toString().contains(a) && sb.toString().contains(b) && sb.toString().contains(c)) {
                if (shortest == null || sb.length() < shortest.length() || (sb.length() == shortest.length() && sb.toString().compareTo(shortest) < 0)) {
                    shortest = sb.toString();
                }
            }
        }

        return shortest;
    }

    private void generatePermutations(String[] strs, int index, List<String> permutations) {
        if (index == strs.length) {
            permutations.add("012");
            return;
        }

        for (int i = index; i < strs.length; i++) {
            swap(strs, index, i);
            generatePermutations(strs, index + 1, permutations);
            swap(strs, index, i);
        }
    }

    private void swap(String[] strs, int i, int j) {
        String temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2800 (Shortest String That Contains Three Strings)?

This page provides optimized solutions for LeetCode problem 2800 (Shortest String That Contains Three Strings) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2800 (Shortest String That Contains Three Strings)?

The time complexity for LeetCode 2800 (Shortest String That Contains Three Strings) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2800 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2800 in Java, C++, or Python.

Back to LeetCode Solutions