New update is available. Click here to update.

Last Updated: 17 Mar, 2021

Difficulty: Moderate

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

```
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 ’.
```

```
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.
```

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

```
1 <= T <= 50
1 <= |S| <= 10^5
1 <= p <= 10^5
Where |S| is the length of the string ‘ S ’
Time Limit: 1sec
```

- 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.

SIMILAR PROBLEMS

Equal Arrays

Posted: 29 Sep, 2022

Difficulty: Moderate

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

Maximize

Posted: 9 Dec, 2022

Difficulty: Easy

Popular Interview Problems: