Construct 'P' Palindromic Strings

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
10 upvotes
Asked in companies
UberSnapdeal Ltd.alibaba

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”.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
ababc
2
pqrst
3
Sample Output 1 :
True
False
Explanation Of Sample Input 1 :
Test Case 1: The given string is “ababc” and p = 2. We can make 2 palindromic strings from the given string as “abba” + “c”.

Test Case 2: We can not make 3 palindromic strings from the given string.
Sample Input 2 :
2
ydredd
5
kkkk   
5
Sample Output 2 :
True
False
Hint

A palindromic string can have at most one character having an odd count.

Approaches (1)
Hash Map Implementation
  • 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.
Time Complexity

O( |S| ), where |S| is the length of the string ‘S’.

 

We are traversing the string linearly for every character of ‘S’.Therefore the time complexity is O( |S| ).

Space Complexity

O( |S| ), where |S| is the length of the string ‘S’.

 

We are using a hash map ‘charCount’ that stores the count of all the distinct characters. The maximum number of distinct characters can be equal to the length of the string. Therefore space complexity is of order O( |S| ). 

Code Solution
(100% EXP penalty)
Construct 'P' Palindromic Strings
Full screen
Console