Last Updated: 11 Nov, 2021

Palindromic Rearrangement

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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

Solve now