Fast, Tricky Python3 Explained
The idea here is to iterate through all possible numbers of parts we could split into, and for each one check if it is possible to split into that many parts. W
The idea here is to iterate through all possible numbers of parts we could split into, and for each one check if it is possible to split into that many parts. We can do this efficiently in O(log10(N)) time where N is the length of the message - (note that log10(N) <= 4 given the constraint of N <= 1000). Thus, worst case we are doing about 4N operations so we can say the overall time complexity is O(N).\n\nNotice that we can determine how much of the message we can add for a certain number of parts based on the prefix and suffix sizes for each iteration of the inner while loop. For example, in parts 1 - 9, we know that the a term in `<a/b>` is one digit, so the length of the suffix starts at simply `len(str(parts)) + 3 + 1`. if parts was 100, we would start out with a suffix length would start at 7, i.e `<1/100>`. Then, we can increment the suffix length for part numbers 10-99, and increment it again for 100-999, and so on. The prefix length will of course be `limit - suffix`. We continue this while loop until we have either expended all of the parts, or expended all of the characters in the message, or the prefix length is 0 (in which case we couldn\'t add any more of the message). Once this while loop is complete, if we used the right number of parts, used the full message, and didn\'t break any of the rules, then it must be possible to construct a valid split and we can simply build one using the simple logic in the `split` method.\n\nPlease upvote if it helps!\n```\nclass Solution:\n    def split(self, message, limit, parts):\n        i, res = 0, []\n        for part in range(1, parts+1):\n            suffix = \'<\' + str(part) + \'/\' + str(parts) + \'>\'\n            prefix_len = limit - len(suffix)\n            res.append(message[i:i+prefix_len] + suffix)\n            i += prefix_len\n        return res\n            \n    def splitMessage(self, message: str, limit: int) -> List[str]:\n        if limit < 6:\n            return []\n        n = len(message)\n        for parts in range(1, n+1):\n            \n            tot_parts = parts\n            cur_parts = 9\n            suffix = len(str(parts)) + 4\n            prefix = limit - suffix\n            mess = n\n            \n            while tot_parts > 0 and mess > 0 and prefix > 0:\n                max_take = cur_parts * prefix\n                if mess > max_take:\n                    tot_parts -= cur_parts\n                    mess -= max_take\n                else:\n                    full_parts = mess // prefix\n                    tot_parts -= full_parts\n                    mess -= full_parts * prefix\n                    if mess > 0:\n                        tot_parts -= 1\n                        mess = 0\n                \n                cur_parts *= 10\n                prefix -= 1\n                suffix += 1\n            \n            if tot_parts == mess == 0:\n                return self.split(message, limit, parts)\n        \n        return []
['Python3']