LeetCode 1400. Construct K palindrome strings

1400. structure K Palindrome strings

Give you a string s And an integer k . Please use s In a string All characters structure k One is not empty Palindrome string .

If you can use s All characters in the structure k Palindrome strings , So please go back to True , Otherwise return to False .

Example 1：

 Input ：s = "annabelle", k = 2
 Output ：true
 explain ： It can be used  s  All characters in the structure  2  Palindrome strings .
 Some feasible construction schemes include ："anna" + "elble","anbna" + "elle","anellena" + "b"

Example 2：

 Input ：s = "leetcode", k = 3
 Output ：false
 explain ： No use  s  All characters in the structure  3  A palindrome string .

Example 3：

 Input ：s = "true", k = 4
 Output ：true
 explain ： The only feasible solution is to let  s  Each character in the form of a single string .

Example 4：

 Input ：s = "yzyzyzyzyzyzyzy", k = 2
 Output ：true
 explain ： All you will need is  z  Put it in a string , be-all  y  Put it in another string . Then both strings are palindromes .

Example 5：

 Input ：s = "cr", k = 7
 Output ：false
 explain ： We don't have enough characters to construct  7  A palindrome string .

Tips ：

• 1 <= s.length <= 10^5
• s All characters in are lowercase letters .
• 1 <= k <= 10^5

Two 、 Method 1

Statistics can make the most and least palindrome substrings , have a look k Whether it's inside

class Solution {
    
    public boolean canConstruct(String s, int k) {
    
        //  The right boundary is the length of the string 
        int right = s.length();
        //  Count the number of occurrences of each character 
        int[] occ = new int[26];
        for (int i = 0; i < right; ++i) {
    
            ++occ[s.charAt(i) - 'a'];
        }
        //  The left boundary is the number of characters with odd number of times 
        int left = 0;
        for (int i = 0; i < 26; ++i) {
    
            if (occ[i] % 2 == 1) {
    
                ++left;
            }
        }
        //  Note that there is no special case of characters with an odd number of times 
        left = Math.max(left, 1);
        return left <= k && k <= right;
    }
}

Complexity analysis

• Time complexity ：O(N+∣Σ∣), among N Is string s The length of ,Σ It's a character set. （ That is, the number of possible character types in the string ）, In this question, the string will only contain lowercase letters , therefore ∣Σ∣=26. We need to s Do a walk , Get the number of occurrences of each character , The time complexity is O(N). After this , We need to iterate through each character , Count the number of characters that appear an odd number of times , The time complexity is O(∣Σ∣).

• Spatial complexity ：O(∣Σ∣). We need to use an array or hash table to store the number of occurrences of each character .