Binary Search solution with digit-count check(It passes "abbababbbaaa aabaa a" test case )
Approach\nBinary Search is not very necessary for this problem. just increase b one by one and check whether there are remain message. It takes O(n) so still ac
# Approach\nBinary Search is not very necessary for this problem. just increase `b` one by one and check whether there are remain message. It takes O(n) so still acceptable.\n\nFor binary search solution, one important thing to notice is that `b` is not monotone for different digit-count.\n\nExample:\nmessage = "abbababbbaaa aabaa a", limit = 8\nA simple BS solution will determine `b` as 11. But cutting into 7 parts also works.\n\nTo resolve this issue, we should **determine BS search range beforehand**. `b` is monotone inside range 1-9,10-99,100-999... \nFirst check whether cut it into 9 part would suffice. If not then there must be at least 10 parts. Then we check if cutting into 99 parts suffice. If not then there must be at least 100 parts. Keep the process until digit-count is found.\n\nAfter `b`\'s digit count is determined, we ensure the BS search range is monotone and can proceed with following process.\n\n\n\n# Code\n```python\nclass Solution:\n    def splitMessage(self, message: str, limit: int) -> List[str]:\n        if limit <= 5: return []\n        \n        # Important: Determine number of digit of b. BS monotone holds for same digit-count  \n        # This will fix the testcase like: message = "abbababbbaaa aabaa a", limit = 8\n        nd = -1\n        for dc in range(1, 7):\n            remain = len(message)\n            for d in range(1, dc+1): \n                if limit - 3 - d - dc < 0: break\n                remain -= (limit - 3 - d - dc)*9*10**(d-1)\n            if remain <= 0:\n                nd = dc\n                break\n        if nd == -1: return []\n        \n        # binary search of b\n        start, end = 10**(nd - 1), 10 ** nd\n        while start != end:\n            mid = (start + end) // 2\n            dc = len(str(mid))\n            remain = len(message) \n            for d in range(1, dc):\n                remain -= (limit - 3 - d - dc)*9*10**(d-1)\n            for i in range(10**(dc-1), mid + 1):\n                remain -= limit - 3 - 2*dc \n                if remain < 0: break\n            # print(start, end, mid, remain)\n            if remain > 0: start = mid + 1\n            else: end = mid\n\n        # construct answer\n        ans = []\n        dc = len(str(start))\n        cur = 0\n        for d in range(1, dc + 1):\n            for i in range(10**(d-1), 10**d):\n                nxt = min(cur + limit - 3 - d - dc, len(message))\n                ans.append(message[cur:nxt] + \'<\' + str(i) + \'/\' + str(start) + \'>\')\n                cur = nxt\n                if nxt >= len(message): break\n                \n        if cur < len(message): return []\n        return ans\n                    \n```
['Python3']