Raju and his string

Easy
0/40
Average time to solve is 20m
profile
Contributed by
0 upvote
Asked in company
SAP India

Problem statement

Raju is playing with his string 'S' of length 'N' consisting of lowercase letters only. He wonders if his string is a good string. Print 1 if 'S' is a good string else print 0.

A string is a good string if the parity of the number of unique characters in the string is equal to the parity of its length.

Parity is the property of an integer of whether it is even or odd.

Example : 
'N' = 5, 'S' = "abacd".

The number of unique characters in 'S' is 4.

The parity of 4 and parity of 'N'( which is 5) is not the same. So, the string 'S' is not a good string. We will print 0.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer 'N', denoting the size of the string 'S'.

The next line contains a string of size 'N'.
Output format : 
For each test case, print 1 if the parity of the number of unique characters is same as the parity of size of the string.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5

The string 'S' consists of lowercase letters only.

The Sum of 'N' over all test cases is <= 10 ^ 5.

Time Limit: 1 sec
Sample Input 1 :
2
4
bake
3
eez
Sample Output 1 :
1
0
Explanation Of Sample Input 1 :
For test  case 1:
Number of unique characters = 4
The parity of 4 is same as 'N'(which is 4).

For test case 2:
Number of unique characters = 2
The parity of 2 is not same as 'N'(which is 3).
Sample Input 2 :
2
5
pizza
6
cheese
Sample Output 2 :
0
1
Hint

How will you calculate the number of unique characters?

Approaches (1)
Optimal

 

Approach :
 

  • There are many ways to calculate the number of unique characters. We will count the number of characters using a boolean array of size MAX_CHARS'(which is 26 here, the number of lowercase letters).
  • Let us say the number of unique characters is 'K'. To check if 'K' and 'N' has the same parity if both are odd or both are even.


 

Algorithm:
 

  • Create a boolean array 'IS_PRESENT' of size 'MAX_CHARS'.
  • Initialise an integer variable 'K' as 0.
  • Loop through all the characters of 'S' from 'i' = 1 to 'i' = 'N':
    • IS_PRESENT[ S[i] - 'a' ] = 1
  • Loop through all the lowercase characters from 'i' = 1 to 'i' = 'MAX_CHARS':
    • Increment 'K' by 1, if 'IS_PRESENT[i]' = 1
  • Return 1 if both 'K' and 'N' are odd or both 'K' and 'N' are even.
  • Else Return 0.
Time Complexity

O(N + MAX_CHARS), where 'N' is the size of the string and 'MAX_CHARS' is the number of lowercase letters.
 

Since we are traversing all the characters of the string 'S' once and all the lowercase letters once. So the Time Complexity of the algorithm is O(N + MAX_CHARS).

Space Complexity

O(MAX_CHARS), where 'MAX_CHARS' is the number of lowercase letters.
 

We have created a boolean array of size 'MAX_CHARS'. So, the Space Complexity is O(MAX_CHARS).

Code Solution
(100% EXP penalty)
Raju and his string
Full screen
Console