2800. Shortest String That Contains Three Strings

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.

class Solution {
public:
    string minimumString(string a, string b, string c) {
        string res = string(a.length() + b.length() + c.length() + 1, '#');
        vector<string> ord{a,b,c};
        sort(begin(ord), end(ord));
        do {
            for(int i = 0; i <= ord[0].length(); i++) {
                string now = ord[0].substr(0,i) + ord[1];
                if(now.length() > res.length()) continue;
                if(now.find(ord[0]) == string::npos) continue;
                for(int j = 0; j <= ord[2].length(); j++) {
                    if(now.length() + j > res.size()) continue;
                    string nnow = now + ord[2].substr(ord[2].length() - j, ord[2].length());
                    if(nnow.find(ord[2]) == string::npos) continue;
                    if(nnow.length() == res.length()) res = min(res, nnow);
                    else res = nnow;
                }
            }
        }while(next_permutation(begin(ord), end(ord)));
        return res;
    }
};