O(1) - Most detailed explanation
The problem is quite simple and interesting as well. Lets start from very basic:\n\nQ. Suppose we are given a string str, and we are free to jumble the characte
The problem is quite simple and interesting as well. Lets start from very basic:\n\n**Q.** Suppose we are given a string ```str```, and we are free to jumble the characters, and we need to tell that wheather ```str``` can be palindrome after jumbling.\n* So, we will keep a track of frequency of each character appeared in ```str``` (with the help of hashmap or array of size 26)\n*  **Now how to check**: \uD83D\uDC49 Even occurances of any character ```c``` is allowed. But there must be either 0 or 1 character with odd occurances\n*  For example: "abba" is palindrome and there are no character with odd frequency. Similarly, "abcba" or "abcccba" is also a palindrome but there is 1 character with odd frequency.\n\nKeeping this in mind: \n* We will store the frequency of each character in input string using hashmap (or array of size 26).\n* We have no issue with even frequency character. As they will always from palindrome.\n* We are concerned with odd freq character. Count that how many character has odd frequency. [say cnt]\n* In order to split input string into \'k\' palindromic string, number of odd freq character must be less than equal to k [or cnt<=k], \n* This is because then only we can distribute each of the odd frequency character in one of the \'k\' strings.\n* Simple! We are done! We are just required to check this condition only.\n\n\n**CODE:**\n```\nclass Solution {\npublic:\n    bool canConstruct(string s, int k) {\n        if(s.size()<k){ return false; } // obvious edge case\n        \n        unordered_map<char, int> m; // {char, freq}\n        for(int i=0; i<s.size(); i++){  m[s[i]]++;  }\n\t\t\n        int cnt=0; // to count odd freq character\n        for(auto& it: m){\n            if(it.second%2==1){ cnt++; }\n        }\n        return (cnt<=k);\n    }\n};\n```\nTime Complexity: O(26) ~ O(1)  ||  Space Complexity: O(26) ~ O(1)
['C']