1400. Construct K Palindrome Strings

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.

Example 1:

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"

Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.
• 1 <= k <= 105

Approach 01:

#include <string>
#include <bitset>
using namespace std;

class Solution {
public:
    bool canConstruct(string inputString, int palindromeCount) {
        // If the string length is less than the required palindromes, it's impossible
        if (inputString.length() < palindromeCount) {
            return false;
        }

        bitset<26> oddFrequencyTracker;  // Tracks characters with odd frequencies
        for (const char currentCharacter : inputString) {
            // Toggle the bit for the current character
            oddFrequencyTracker.flip(currentCharacter - 'a');
        }

        // Check if the count of odd-frequency characters is less than or equal to the required palindromes
        return oddFrequencyTracker.count() <= palindromeCount;
    }
};

class Solution:
    def canConstruct(self, inputString: str, palindromeCount: int) -> bool:
        # If the string length is less than the required palindromes, it's impossible
        if len(inputString) < palindromeCount:
            return False

        oddFrequencyTracker = set()  # Tracks characters with odd frequencies
        for currentCharacter in inputString:
            # Toggle the presence of the current character in the set
            if currentCharacter in oddFrequencyTracker:
                oddFrequencyTracker.remove(currentCharacter)
            else:
                oddFrequencyTracker.add(currentCharacter)

        # Check if the count of odd-frequency characters is less than or equal to the required palindromes
        return len(oddFrequencyTracker) <= palindromeCount

Time Complexity:

• Character Frequency Tracking:

  The loop iterates through all characters of the input string, performing a constant-time operation for each character. This results in \( O(n) \), where \( n \) is the length of the input string.

• Bitset Operations:

  Toggling a bit and counting set bits in a fixed-size bitset are \( O(1) \) operations.

• Overall Time Complexity:

  \( O(n) \).

Space Complexity:

• Bitset Storage:

  The bitset used for tracking character frequencies is of fixed size (26 bits for lowercase English letters), resulting in \( O(1) \) space.

• Input String:

  The input string is read-only and does not require additional storage.

• Overall Space Complexity:

  \( O(1) \).