[c++] sliding window + suffix array = O(n log n) time
Basic algorithm (O(n^2) time, O(1) space):\nc++\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string_view s, int k) {\n        // time = O(n
Basic algorithm (O(n^2) time, O(1) space):\n```c++\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string_view s, int k) {\n        // time = O(n^2), space = O(1)\n        string_view ret;\n        const unsigned n = s.length();\n        unsigned len = n + 1;\n        // find shortest possible beautiful substring\n        for (unsigned i = 0, j = 0, n1 = 0; i < n; ++i) {\n            n1 += s[i] - \'0\';\n            while(n1 > k)\n                n1 -= s[j++] - \'0\';\n            while(j <= i && s[j] == \'0\')\n                ++j;\n            if (n1 == k)\n                len = min(len, i + 1 - j);\n        } // O(n)\n        if (len > n) // nothing found\n            return string();\n        unsigned n1 = 0;\n        unsigned minpos = n;\n        unsigned minorder = n;\n        for (unsigned i = 0; i < len; ++i)\n            n1 += s[i] - \'0\';\n        if (n1 == k) {\n            ret = s.substr(0, len);\n        }\n        for (unsigned i = len; i < s.length(); ++i) {\n            n1 -= s[i - len] - \'0\';\n            n1 += s[i] - \'0\';\n            if (n1 == k) {\n                if(ret.empty() || ret.compare(0, len, s, i - len + 1, len) > 0)\n                    ret = s.substr(i - len + 1, len);\n            }\n        } // O((n - len)*len) = O(n^2)\n        return string(ret);\n    }\n};\n```\n0ms (faster than 100%), 6.6M (smaller than 100%)\n\nFirst, we discover minimum length of beautiful string (O(n) time, O(1) space), then choose lexicigraphically minimum beautiful string with this minimum length (we need at most O(n - len) comparisons, each taking O(len) time). Hence, it\'s still O(n^2) time.\nWe can do better with suffix arrays:\n```c++\ntemplate <typename V, typename Size_Type = typename V::size_type>\nstruct SuffixArray { // https://cp-algorithms.com/string/suffix-array.html\n  typedef Size_Type size_type;\n  vector < size_type > p;\n  SuffixArray(const V & s,\n\tconst size_type alphabet = static_cast<size_type>(1) << (8*sizeof(typename V::value_type)),\n\tconst typename V::value_type minc = 0) {\n    // O(n log n) time, O(n) space\n    size_type n = s.size();\n    static_assert(sizeof(typename V::value_type) < sizeof(size_type));\n    vector < size_type > cnt(max(alphabet, n), 0), c(n), cn(n);\n    p.resize(n);\n    // counter sort array p, O(n)\n    for (size_type i = 0; i < n; i++) cnt[s[i] - minc]++;\n    for (size_type i = 1; i < alphabet; i++) cnt[i] += cnt[i - 1];\n    for (size_type i = 0; i < n; i++) p[--cnt[s[i] - minc]] = i;\n    c[p[0]] = 0;\n    size_type classes = 1;\n    for (size_type i = 1; i < n; i++) {\n      if (s[p[i]] != s[p[i - 1]]) classes++;\n      c[p[i]] = classes - 1;\n    }\n    vector < size_type > pn(n);\n    for (size_type two_pow_h = 1; two_pow_h < n; two_pow_h <<= 1) {\n      for (size_type i = 0; i < n; i++) {\n        pn[i] = p[i] + n - two_pow_h;\n    \tif (pn[i] >= n) pn[i] -= n;\n      }\n      fill_n(cnt.begin(), classes, 0);\n      for (size_type i = 0; i < n; i++) cnt[c[pn[i]]]++;\n      for (size_type i = 1; i < classes; i++) cnt[i] += cnt[i - 1];\n      for (size_type i = n; i-- > 0; ) p[--cnt[c[pn[i]]]] = pn[i];\n      cn[p[0]] = 0;\n      classes = 1;\n      for (size_type i = 1; i < n; i++) {\n\t    if (c[p[i]] != c[p[i - 1]])\n          ++classes;\n\t    else {\n          auto pi_next = p[i] + two_pow_h;\n          if (pi_next >= n) pi_next -= n;\n          auto pi1_next = p[i - 1] + two_pow_h;\n          if (pi1_next >= n) pi1_next -= n;\n          if (c[pi_next] != c[pi1_next])\n            ++classes;\n        }\n        cn[p[i]] = classes - 1;\n      }\n      c.swap(cn);\n    }\n  }\n};\nclass Solution {\npublic:\n    string shortestBeautifulSubstring(string_view s, int k) {\n        // time = O(n log n), space = O(n)\n        const unsigned n = s.length();\n        unsigned len = n + 1;\n        // find shortest possible beautiful substring\n        for (unsigned i = 0, j = 0, n1 = 0; i < n; ++i) {\n            n1 += s[i] - \'0\';\n            while(n1 > k)\n                n1 -= s[j++] - \'0\';\n            while(j <= i && s[j] == \'0\')\n                ++j;\n            if (n1 == k)\n                len = min(len, i + 1 - j);\n        } // O(n)\n        if (len > n) // nothing found\n            return string();\n        SuffixArray<string_view, unsigned> sa(s, 2, \'0\');\n        vector<unsigned> order(n); // maps position to lexicographical order\n        for (unsigned i = 0; i < n; ++i) // invert sa.p\n            order[sa.p[i]] = i;\n        unsigned n1 = 0;\n        unsigned minpos = n;\n        unsigned minorder = n;\n        for (unsigned i = 0; i < len; ++i)\n            n1 += s[i] - \'0\';\n        if (n1 == k) {\n            minpos = 0;\n            minorder = order[0];\n        }\n        for (unsigned i = len; i < s.length(); ++i) {\n            n1 -= s[i - len] - \'0\';\n            n1 += s[i] - \'0\';\n            if (n1 == k) {\n\t\t\t    unsigned pos = i - len + 1;\n                if (auto o = order[pos]; o < minorder) { // instead of comparing substrings, we just compare lexicographical order of arrays\n                    minpos = pos;\n                    minorder = o;\n                }\n            }\n        } // O(n - len)\n\t\tassert(minpos + len <= n);\n        return string(s.substr(minpos, len));\n    }\n};\n```\n4ms time (still faster than 100%), 7MB space (better than 89%, ok).\n\nAs usually, for small constraints dumb simple algorithms outperforms overly smart ones with large overhead.\nBut it would be completely different with n = 10^5 or something :-)
['C', 'Suffix Array']