Detailed explanation with code | Both O(n) and Binary Search solution | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s pretty obvious from the question that the key thing we need to find out is minimu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s pretty obvious from the question that the key thing we need to find out is **minimum number of total splits**. If we know in how many parts we can split the message so that every part except the last one satisfying the limit condition, we can easily build the answer.\nThe bruteforce will be trying every possible total number of part (starting from 1..) and check which one is satisfying the condition. But that will be too much.\n\nBut but but... do we really need to know the exact number of total splits? let\'s take one example\n\nString = "this is really a very awesome message",  limit=9\n\nle\'s try splitting the string in **7** parts:\n`"this<1/7>", " is <2/7>", "real<3/7>", "ly a<4/7>", " ver<5/7>", "y aw<6/7>", "esom<7/7>", "e me<8/7>", "ssag<9/7>", "e<10/7>"`  -> not possible (need 10 parts)\n\nlet\'s try with **9** parts:\n`"this<1/9>", " is <2/9>", "real<3/9>", "ly a<4/9>", " ver<5/9>", "y aw<6/9>", "esom<7/9>", "e me<8/9>", "ssag<9/9>", "e<10/9>"`  -> not possible (need 10 parts)\n\n\nlet\'s try with **10** parts:\n`"thi<1/10>","s i<2/10>","s r<3/10>","eal<4/10>","ly <5/10>","a v<6/10>","ery<7/10>"," aw<8/10>","eso<9/10>","me<10/10>"," m<11/10>","es<12/10>","sa<13/10>", "ge<14/10>"` -> not possible (need 14 parts)\n<br>wait..what? why 10 part is not working? -> becuse number of characters required by the total part number has increased :)\n\nlet\'s try with **14** parts:\n`"thi<1/14>","s i<2/14>","s r<3/14>","eal<4/14>","ly <5/14>","a v<6/14>","ery<7/14>"," aw<8/14>","eso<9/14>","me<10/14>"," m<11/14>","es<12/14>","sa<13/14>","ge<14/14>"` -> possible\n\nlet\'s try with **15** parts:\n`"thi<1/15>","s i<2/15>","s r<3/15>","eal<4/15>","ly <5/15>","a v<6/15>","ery<7/15>"," aw<8/15>","eso<9/15>","me<10/15>"," m<11/15>","es<12/15>","sa<13/15>","ge<14/15>"` -> not possible (need 14 parts)\n\nKey Observations:\n1. While trying with 7 or 9 or you can try with any single digit part number, we will always see that the actual number of parts require is 10\n2. Similarly, while trying with any 2 digit part number, we will always see require total part is 14.\n\nThought:\n1. The number of parts depends on the number of digits of `total parts`, as that will determine how many character of the message we can put into a single part. And ultimately that will decide how many actual total parts we will require.\n2. Therefor, if we try to split the message into a total number of parts with `d` digits and after splitting we get the number of digits in actual `total number of parts`(let\'s say b) d digits only, then we know b is the exact total number of parts we require (becaseue it satisfying the condition of d digits). \n\nModified Problem Statement:\n1. Find total number of digits require for b\n\n\n# Approach I\n<!-- Describe your approach to solving the problem. -->\nFrom the constraint we can observer that `message.length<=10^4`, therefor we can safely deduce from that b will be always lesser than `10^4`, i.e., number of digits in b will be atmost `5` (10000 -> 5 digits).\n\nWith this small range (1 to 5), we can easily check for each number of digits which one is satisfying the condition. (we require the minimum number of digits)\n\n# Code\n```\nclass Solution {\npublic:\n    int isValidTotalPart(string& message, int limit, int numberOfDigit) {\n        int a = 0, i=0;\n        limit = limit - 3 - numberOfDigit; // substract size of \'</>\' and b\n        if(limit<=0) return 0;\n        while(i<message.size()) {\n            a++; // -> part number\n            int l = limit - to_string(a).size(); // -> substract size of a\n            if(l<=0) return 0; //-> if there is no space of message, then it\'s not possible\n            i+=l; //-> use remaining space for message\n        }\n        return a; //-> return how many actual total parts required\n    }\n\n    vector<string> splitMessage(string message, int limit) {\n        int b = 0;\n        for(int numberOfDigit=1; numberOfDigit<=5; numberOfDigit++) {\n            int totalPart = isValidTotalPart(message,limit, numberOfDigit);\n            if(totalPart>0 && to_string(totalPart).size()==numberOfDigit) { // check if number of digits in actual totalPart is equal to what we tried\n                b=totalPart;\n                break;\n            }\n        }\n\n        if(b==0) return {};\n\n        // build the answer\n        vector<string> ans(b); // we know b number of parts will be required\n        limit = limit - 3 - to_string(b).size();\n        int i=0;\n        for(int a=1; a<=b; a++) {\n            int l = limit - to_string(a).size();\n            ans[a-1] = message.substr(i, l) + "<" + to_string(a) + "/" + to_string(b) + ">";\n            i+=l;\n        }\n\n        return ans;\n    }\n};\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n) -> `isValidTotalPart()` will be called 5 times and each pass will take O(n) where n is size of message\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) - for storing the `ans` vector\n\n---\n\n# Approach II (Binary Search)\n<!-- Describe your approach to solving the problem. -->\nIf the range for number of digits is quite large, then the above approach will take O(n*k), where k is range of digits. We can optimise it further in that scenario by performing binary search on the range of k.\n\n# Code\n```\nclass Solution {\npublic:\n    int isValidTotalPart(string& message, int limit, int numberOfDigit) {\n        int a = 0, i=0;\n        limit = limit - 3 - numberOfDigit; // substract size of \'</>\' and b\n        if(limit<=0) return 0;\n        while(i<message.size()) {\n            a++; // -> part number\n            int l = limit - to_string(a).size(); // -> substract size of a\n            if(l<=0) return 0; //-> if there is no space of message, then it\'s not possible\n            i+=l; //-> use remaining space for message\n        }\n        return a; //-> return how many actual total parts required\n    }\n\n    vector<string> splitMessage(string message, int limit) {\n        int l = 1, r = 5;\n        int b = 0;\n\n        while(l<=r) {\n            int mid = l+(r-l)/2;\n            int totalPart = isValidTotalPart(message, limit, mid);\n\n            if(totalPart==0 || to_string(totalPart).size()<mid) r=mid-1; //if number of digits require is less than what we have tried for, shift the search space to left\n            else if(to_string(totalPart).size()==mid) {\n                b = totalPart;\n                r=mid-1; // shift to left to search for lesser number of digit\n            } // if more number of digits require is more, shift search space to right\n            else l=mid+1;\n        }\n        //cout<<"Total part "<<b<<endl;\n\n        if(b==0) return {};\n\n\n        // build the answer\n        vector<string> ans(b); // we know b number of parts will be \n        limit = limit - 3 - to_string(b).size();\n        int i=0;\n        for(int a=1; a<=b; a++) {\n            int l = limit - to_string(a).size();\n            ans[a-1] = message.substr(i, l) + "<" + to_string(a) + "/" + to_string(b) + ">";\n            i+=l;\n        }\n\n        return ans;\n    }\n};\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlogk) -> `isValidTotalPart()` will be called log(k) times and each pass will take O(n) where k is the range of number of digits and n is the message size\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) - for storing the `ans` vector\n
['Binary Search', 'C++']