New update is available. Click here to update.

Construct 'P' Palindromic Strings

PROBLEM STATEMENT

Given a string ‘S’ and an integer ‘ p ’. You need to find if you can make ‘ p ’ number of non-empty palindromic strings by using all the characters of string ‘ S ’. Note that you can use a character only once and if there are more than once occurrence of that character you can use it that many times only.

For Example :

If the given string is “ninjas” and p = 4 then we can make 4 palindromic strings as “nin” + “j” + “a” + “s”.

Input Format :

The first line contains ‘T’ denoting the number of test cases.

The first line of each test case contains the string ‘S’.

The second line of each test case contains the integer ‘ p ’.

Output Format :

For each test case, print “True” if it is possible to construct ‘ p ’ palindromic strings from all letters of string ‘S’ and print “False” if it is not possible.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= |S| <= 10^5
1 <= p <= 10^5

Where |S| is the length of the string ‘ S ’

Time Limit: 1sec

Approach 1

We will use the idea that a palindromic string can have at most one character having an odd count.
So the minimum number of palindromic strings that will be made by using all letters of ‘S’ will be equal to the number of characters in ‘S’ that have an odd count.
Now if this number of characters(having an odd count) is more than ‘ p ’ i.e minimum palindromic strings is more than ‘ p ’, then we can not make ‘p’ palindromic strings.
Otherwise, we can construct ‘ p ’ palindromic strings.

Algorithm

If the length of the string is less than ‘ p ’, return false.
Initialize an unordered hashmap ‘charCount’ that maps from ‘char’ to ‘int’ to store the count of every character in ‘S’.
Run a loop for all characters of the string
- Increment the value for every character.
Take a variable ‘oddCount’ to store the count of characters having an odd count.
For every key in hashmap ‘charCount’, if the value at any key is odd, increment ‘oddCount’.
If ‘oddCount’ is greater than ‘ p ’ return false.
Otherwise, return true.

Try Problem

Construct 'P' Palindromic Strings

PROBLEM STATEMENT

For Example :

Input Format :

Output Format :

Note :

Constraints :

Approach 1

Interested in Coding Ninjas Flagship Courses?