Construct k palindrome strings - Easy Explanation 🔜
Intuition

If the number of palindrome k is greater than the length of the string s, then no such k palindrome can be made from the string s.


If the number of
# Intuition
1. If the number of palindrome k is greater than the length of the string s, then no such k palindrome can be made from the string s.

1. If the number of palindrome k is equal to the length of the string s, then each single character in the string s is actually palindrome.

1. Atleast each palindrome constructed can have atmost one character with the odd Frequency.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach

**Initialization**:

Initialize n to be the number of characters in the string s.

    int n=s.length();

**Precondition**:

Check if the number of palindrome k is greater than the length of the string s , then return false.

    if(k>n)
        return false;

Check if the number of palindrome k equals the length of the string s, then return true.

    if(k==n)
        return true;

**Calculate frequency of each character in string s**:

Initialize count to be the integer array with the size of 26.

    int[] count=new int[26];

Iterate through all the characters in the string s,then update the count of each characters in the count array.

    for(char ch:s.toCharArray())
    {
        count[ch-'a']++;
    }

**Find number of characters with odd Frequency**:

Iterate through all the elements of the count array and update the OddCnt if the count of the frequency of each character is odd 
(count[i]%2!=0).

    int oddCnt=0;
    for(int i=0;i<26;i++)
    {
        if(count[i]%2!=0)
            oddCnt++;
    }

**Finalizing result**:

If the characters with odd frequency is less than or equal to k and k should be less than or equal to n(this means that each palindrome must have atmost one odd Frequency), then return true.
 
    if(oddCnt<=k && k<=n)
          return true;

Otherwise return false, since no such k palindromic strings can be formed from the string of length n.

    return false;
<!-- Describe your approach to solving the problem. -->

# Complexity
- **Time complexity**: **O(n)**.
    n -> number of characters in the string s.

**Length of the string s**: **O(n)**.

Calculating the length of the string s iterates through all the elements of the string s.Hence it's time complexity is **O(n)**.

**Iterate through string to populate frequency**: **O(n)**.

To populate frequency of the characters in the count array, iterates through all the characters of the string s, Hence it takes 
**O(n) time**.

**Iterate through count array**: **O(1)**.

Iterate through the count array 26 times and hence it takes constant time complexity of **O(26) which will be O(1)**.

**Overall Time Complexity**: **O(n)**.

Hence the overall time complexity of the above program can be 
**O(n)+O(n)+O(1) = O(n) time**.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- ***Space complexity***: **O(1)**.

   The count array is used whose size is independent of the input size n, hence it takes **constant space**.

   Hence it's space complexity is **O(1)**.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public boolean canConstruct(String s, int k) {
        int n=s.length();
        if(k>n)
          return false;
        if(k==n)
          return true;
        int[] count=new int[26];
        for(char ch:s.toCharArray())
        {
            count[ch-'a']++;
        }
        int oddCnt=0;
        for(int i=0;i<26;i++)
        {
            if(count[i]%2!=0)
              oddCnt++;
        }
        if(oddCnt<=k && k<=n)
          return true;
        return false;
    }
}
```
['String', 'Counting', 'Java']