Palindromic Rearrangement

Easy
0/40
4 upvotes
Asked in companies
AppleRooter Sports Technology Pvt Ltd

Problem statement

Ninja’s Friend came up again with a new challenge to test Ninja’s intelligence. There is a string ‘S’ consisting of ‘N’ small letters. Ninja’s task is to tell whether it is possible to rearrange the string so that it becomes palindromic. Can you help Ninja to solve this problem?

A string is said to be palindrome if it reads the same backward as forward. For example: naman, rotor, etc.

For Example 
If N=5 and given string S is “rtoor”, the string can be rearranged as “rotor,” which is palindromic.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, 'N’, denoting the length of the given string.

The second line contains the given string ‘S’.
Output Format: 
For each test case, print ‘YES’ if the string can be rearranged into a palindromic string, else print ‘NO’.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^6.
S consists of only lowercase alphabets.    

Time limit: 1 sec
Sample Input 1:
2
5
rtoor
3
arm
Sample Output 1:
YES
NO
Explanation of sample input 1:
For the first test case,

The given string can be rearranged as “rotor,” which is a palindromic string.
Hence, the answer is YES. 

For the second test case:

The given string cannot be rearranged as a palindromic string
Hence, the answer is NO.
Sample Input 2:
2
15
acabeececbeedad
10
ccdecaeeba
Sample Output 2:
NO
NO
Hint

Check the frequency of each character.

Approaches (1)
Character frequency.

In this approach, we will iterate through the whole string and store the frequency of each character. As we know, a palindromic string can have at most one character with an odd frequency. So, we will count the number of characters with odd frequencies, and if the count is greater than 1, the palindromic rearrangement is impossible. Else, palindromic rearrangement is possible.

 

Algorithm:

  • Declare a frequency array ‘FREQ’ of size 26 to store the frequencies of all characters.
  • Set all values of ‘FREQ’ to 0.
  • For i in range 0 to ‘N’, do the following:
    • Increment frequency of S[i] by 1.
  • Declare ‘ODD_FREQ’ to store the number of characters having an odd frequency.
  • For i in range 0 to 25:
    • If FREQ[i] is odd:
      • Set ODD_FREQ’ as ODD_FREQ’ +1.
  • If ODD_FREQ’ is greater than 1:
    • Return ‘NO’.
  • Return ‘YES’.
Time Complexity

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

 

In this approach, we are traversing the whole string ‘S’ to count the frequency of each character, which takes O(N) operations. Hence, the overall time complexity is O(N).

Space Complexity

O(1)

 

In this approach, we store the frequency in the ‘FREQ’ array of size 26(constant space). Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Palindromic Rearrangement
Full screen
Console