leetcode/problems-cpp/special-binary-string/solution.h at main · goodstudyqaq/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class Solution {
   public:
    string makeLargestSpecial(string s) {
        if (s.size() <= 2) return s;

        int left = 0;
        int n = s.size();
        int score = 0;
        vector<string> ans;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1')
                score++;
            else {
                score--;
                if (score == 0) {
                    string go = s.substr(left + 1, i - (left + 1));
                    string tmp = makeLargestSpecial(go);
                    ans.push_back("1" + tmp + "0");
                    left = i + 1;
                }
            }
        }

        sort(ans.begin(), ans.end(), greater<string>());
        string res = accumulate(ans.begin(), ans.end(), ""s);
        return res;
    }
};