Binary Search || Simple Approach || C++ || Explaination || Clear Code
In this problem, we are sure that if we give 1 token to every element we get the one possible distribution but it is not the ans, but if we take it as one possi
In this problem, we are sure that if we give 1 token to every element we get the one possible distribution but it is not the ans, but if we take it as one possible chance of answer so our distribution will be from 1 to n (length of the string). \nNow first we check for the middle one. If the answer is possible we can return it. but If answer is not possible from that partition and the size of string is greater than the token size than it is sure that the ans present in the lower half then we skip it upper and check for the lower half and vice versa.\nFor elimination the halfs we use binary search O(log n) and to check the possibility of ans we traverse to whole string O(n).\nSo the time Complexity of program is O(n log n).\n\n\n\n```\nclass Solution {\npublic:\n    vector<string> splitMessage(string message, int limit) {\n        return solution(message,limit,message.size());\n    }\nprivate:\n    vector<string> solution(string m,int limit,int n) {\n        int i=1,j=n;\n        while(i<=j) {\n            int mid = (i+j)/2;\n            pair<vector<string>,int> ans = get_str(m,limit,mid);\n            if(ans.second == 0) return ans.first;\n            else if(ans.second==-1) i = mid+1;\n            else j = mid-1;\n        }\n        return {};\n    }\n    \n    pair<vector<string>,int> get_str(string m,int limit,int total) {\n        string temp = to_string(total);\n        string pre = "";\n        int num = 1;\n        string check = to_string(num);\n        vector<string> ans;\n        for(int i=0 ; i<m.length() ; ++i) {\n            if(check.length()+temp.length()+3 >= limit) return {{},-1};\n            if(pre.size()+check.length()+temp.length()+3 == limit) {\n                string insert = pre;\n                insert.push_back(\'<\');\n                insert.append(check);\n                insert.push_back(\'/\');\n                insert.append(temp);\n                insert.push_back(\'>\');\n                ans.push_back(insert);\n                pre = "";\n                i-=1;\n                num+=1;\n                check = to_string(num);\n            }\n            else {\n                pre.push_back(m[i]);\n            }\n        }\n        string insert = pre;\n        insert.push_back(\'<\');\n        insert.append(check);\n        insert.push_back(\'/\');\n        insert.append(temp);\n        insert.push_back(\'>\');\n        ans.push_back(insert);\n        if(num == total) return {ans,0};\n        else if(num > total) return {{},-1};\n        return {{},1};\n    }\n};\n```
['Binary Search', 'C++']