Leetcode: Construct K Palindrome Strings

This question is extremely common at Uber. Here it is:

Given a string s and integer k, you should construct k non-empty palindrome strings using all the characters in S. Return True if you can use all the characters in s to construct k palindrome strings. Otherwise, return false.

Here are some examples: 

Example 1: 

Input:

s = "annabelle" k = 2

Output: 

true

Explanation:

You can construct two palindromes using all the characters in S. The strings are "anna", "elble", "anbna", "elle", "anellena", "b". 

Another string is "leetcode", k = 3, and it is impossible to construct 3 palindromes using all of the characters in S. 

Here are the hints:

If s.length < k, then we cannot construct k strings from s and the answer, as a result, is false. So this would be used as a base case. 

If the number of characters that have odd counts is greater than k, then the minimum of palindrome strings we can construct is > k and the answer is false. 

Otherwise, you can construct exactly k palindrome strings and the answer is true. 

So lee215 came up with an intuition of the algorithm. 

We want to make sure the number of odd characters is less than or equal to k, and that k is less than or equal to s.length(). 

There must be at least one palinldrome if one character has odd time occurences such as "a", "b", "c", "d", "e", etc. 

If we have one character in each palindrome, we will have at most s.length palindromes so k <= s.length(). 

racecar

e

cec

aceca

racecar

(this has 5 or n/2 + 1 different substrings). 

public boolean canConstruct (String s, int k) {

    int odd = 0;

    int n = s.length(); 

    int[] count = new int[26]; 

    for(int i = 0; i < n; i++) {

        //index in the alphabet

        int alphabetIndex = s.charAt(i) - 'a';

        //determine parity 

        count[alphabetIndex] = count[alphabetIndex] ^ 1;

        //increment and decrement odd index based on the parity bit

        if(count[alphabetIndex] > 0) {

            odd++;

        } else {

            odd--;

        }

    }

     //return if there are less than k odd digits and that k is less than the length of the substring 

    return (odd <= k) && (k <= n); 

}

Palindromes have to have at least one character whose frequency is odd. Every other character's frequency has to be even.