Binary Search
This is an old problem known as SMS split (SMS messages are limited to 160 characters).\n\nWe can use a binary search to find out the number of messages. We jus
This is an old problem known as SMS split (SMS messages are limited to 160 characters).\n\nWe can use a binary search to find out the number of messages. We just need to make this search efficient (e.g. no string creation).\n\n> Note that first we need to find the smallest number of digits in `b`, e.g. 1 (up to 9 parts), 2 (up to 99), 3 (up to 999), and so on.\n\nKnowing the number of messages, we then can build out splits.\n\n**C++**\n```cpp\nbool binarySearch(int sz, int limit, int m) {\n    int len_a = 1, up = 9, len_b = to_string(m).size();\n    for (int a = 1; a <= m && sz > 0; ++a) {\n        sz -= limit - 3 - len_a - len_b;\n        if (a == up) {\n            ++len_a;\n            up = up * 10 + 9;\n        }\n    }\n    return sz <= 0;\n}\nvector<string> splitMessage(string mess, int limit) {\n    int l = 1, r = 9, sz = mess.size();\n    vector<string> res;\n    while (l <= sz && !binarySearch(sz, limit, r)) {\n        l *= 10;\n        r = min(r * 10 + 9, sz + 1);\n    }\n    if (l <= sz) {\n        while (l < r)\n            if (int m = (l + r) / 2; binarySearch(sz, limit, m))\n                r = m;\n            else\n                l = m + 1;\n        for (int i = 0, a = 1; a <= l; ++a) {\n            string suff = "<" + to_string(a) + "/" + to_string(l) + ">";\n            res.push_back(mess.substr(i, limit - suff.size()) + suff);\n            i += limit - suff.size();\n        }\n    }\n    return res;\n}\n```
['C']