Собеседования по алгоритмам: максимальная конкатенация

Про сортировку уже успели написать, предложу другой более наглядный, но медленный алгоритм.

Давайте составлять ответ итеративно, пусть мы каким то образом получили ответ используя первые i чисел, теперь хотим понять как изменится ответ если будем использовать i + 1 чисел. Для этого достаточно перебрать все возможные позиции вставки i + 1 числа и выбрать ту что дает максимум.

Вот мое решение для задачи https://leetcode.com/problems/largest-number/description/

string largestNumber(vector<int>& nums) {
    vector<string> order;
    for (int i = 0; i < nums.size(); ++i) {
        int insert_pos = 0;
        string pref, suf, mx;
        for (auto& str : order) {
            suf += str;
        }
        for (int j = 0; j <= order.size(); ++j) {
            string cur = pref + to_string(nums[i]) + suf;
            if (cur > mx) {
                insert_pos = j;
                mx = cur;
            }
            if (j < order.size()) {
                suf = suf.substr(order[j].size());
                pref += order[j];
            }
        }
        order.insert(order.begin() + insert_pos, to_string(nums[i]));
    }
    string ans;
    for (auto& str : order) {
        ans += str;
    }
    if (ans.front() == '0') {
        return "0";
    }
    return ans;
}

Готовимся к алгоритмическому big-tech интервью: язык имеет значение

А зачем такая доп проверка? По условиям задачи на leetcode нам гарантируется, что строка состоит только из символом '()[]{}'. Так что достаточно только проверить что скобка открывающаяся, если же провалились ниже в цепочке if то это уже точно закрывающаяся скобка.

Готовимся к алгоритмическому big-tech интервью: язык имеет значение

Раз уж тут конкурс на самое короткое решение, вот еще один плюсовый вариант

bool isValid(string s) {
    stack<char> q;
    string u = ")(][}{";
    for (char c : s) {
        auto p = u.find(c);
        if (p & 1) {
            q.push(u[p - 1]);
        } else if (q.empty() || q.top() != c) {
            return false;
        } else {
            q.pop();
        }
    }
    return q.empty();
}