Construct K Palindrome Strings LeetCode Solution

Difficulty Level Medium
Frequently asked in UberViews 2037

Problem Statement

Construct K Palindrome Strings LeetCode Solution – Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise.

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two

palindromes using all characters

 in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Explanation

The trick is to understand that the characters which occur an odd number of times will form a separate palindromic string each time consisting of either a single character or being present in the mid of a string. So, if the count of odd characters happens to be more than k, we return a false and likewise follow.

Also if the number of characters in s is less than k then it’s in no way possible to make k palindromic strings out of it.

For all other cases, we can make k palindromic strings.

Count the character having an odd frequency(countodd)
if(countodd<=k) return true;
else
return false

Code

C++ Code For Construct K Palindrome Strings

class Solution {
public:
    bool canConstruct(string s, int k) {
        unordered_map<char,int> freq;
        for(char ch:s)
        {
            freq[ch]++;
        }
        int oddCount=0;
        for(auto pr:freq)
        {
            if(pr.second%2)
            {
                oddCount++;
            }
        }
        return oddCount<=k&&k<=s.length();
    }
};

Java Code For Construct K Palindrome Strings

class Solution {
    public boolean canConstruct(String s, int k) {
        int n = s.length();
        if (n==k) return true;
        else if (n<k) return false;
        int [] cnt = new int[26];
        for (int i = 0; i<n; i++) cnt[s.charAt(i)-'a']++;
        int odd_chars = 0;
        for (int i = 0; i<26; i++) {
            if (cnt[i]==0) continue;
            if (cnt[i]%2!=0) odd_chars++;
        }
        if (odd_chars>k) return false;  
        else return true;
    }
}

Python Code For Construct K Palindrome Strings

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        count = collections.Counter(s)
        odd = 0
        for i in count:
            if count[i] % 2:
                odd += 1
                if odd > k:return False
        return len(s) >=  k

Complexity Analysis for Construct K Palindrome Strings LeetCode Solution

Time Complexity

O(N) as we need to visit each character to calculate its count.

Space Complexity

O(N) we store the frequencies of characters in a hash-map or frequency array so it would take O(n) space.

Reference: https://en.wikipedia.org/wiki/Palindrome

Translate »