[C++] Direct search for minimum target part number
Think of the string "xxxx<a/b>" where b is a fixed upper bound with a < b.\nGiven a limit, one must reserve 3 characters for < / >.\nThe spaces allowed for putt
Think of the string `"xxxx<a/b>"` where b is a fixed upper bound with `a < b`.\nGiven a limit, one must reserve 3 characters for `<` `/` `>`.\nThe spaces allowed for putting characters would be `limit - 3 - len(b) - len(a)`.\n![image](https://assets.leetcode.com/users/images/54b6dc8c-e784-41a9-9d56-311dd02f6021_1668274711.8729708.png)\n\n\n\nDue to the observation, we try to fix baseDigit and search for the minium part number through `getMinumPartNum()`.\nThis function bascially fulfills the following logic:\n\nWe use variable `baseDigit` for the digit count of upper bound b.\nAssume the baseDigit is 3, we try to consume the characters from message.\nPart Index: [1-9], 9 parts with len(a) =1, each consumes `limit - 3 - baseDigit - 1` characters.\nPart Index: [10 - 99], 90 parts with len(a) = 2 , each consumes `limit - 3 - baseDigit - 2` characters.\nIf there is no enough characters before reaching index 100, we can return false to early stop.\nFor the remaing part count with index >= 100, it would be `ceil(remainCharCnt / (limit - 3 - 2 * baseDigit))`\nSince there is at most 999 parts with baseDigit = 3, we still need to check if the final part number does not exceed this contraint.\n\nGiven that we\'ve found the minimum part number, to form the final part vector would be trivial.\n\n```\nclass Solution {\npublic:\n    vector<string> splitMessage(string message, int limit) {\n        int n = message.size();\n        int baseDigit = 1;\n        int minPartNum = INT_MAX;\n        while (limit - 3 - 2 * baseDigit > 0) {\n            if (getMinumPartNum(n, baseDigit, limit, minPartNum))\n                break;\n            baseDigit++;\n        }\n        if (minPartNum == INT_MAX) return {};\n        \n        vector<string> ans;\n        formPart(message, limit, minPartNum, ans);\n        return ans;\n    }\n    \n    bool getMinumPartNum(int n, int baseDigit, int limit, int &minPartNum) {\n        double remainCharCnt = n;\n        int cnt = 0;\n        for (int d = 1; d <= baseDigit; d++) {\n            if (d != baseDigit) {\n                remainCharCnt -= 9 * pow(10, d - 1) * (limit - 3 - baseDigit - d);\n                if (remainCharCnt < 0) return false;\n            } else\n                cnt = ceil(remainCharCnt/ (limit - 3 - 2 * baseDigit));\n        }\n\n        int finalPartNum = pow(10, baseDigit - 1) - 1 + cnt;\n        if (finalPartNum >= pow(10, baseDigit)) return false;\n        minPartNum = finalPartNum; \n        return true;\n    }\n    \n    void formPart(string message, int limit, int partNum, vector<string> &ans) {\n        int idx = 0;\n        int n = message.size();\n        for (int i = 1; i <= partNum; i++) {\n            string postfix = "<" + to_string(i) + "/" + to_string(partNum) + ">";\n            int remain = limit - postfix.size();\n            string token = message.substr(idx, min(remain, n - idx)) + postfix;\n            idx += remain;\n            ans.push_back(token);\n        }   \n    }\n};\n```
['C']