Problem of the day
You are given a string 'S'. You perform the following operations:
1. Split 'S' into three non-empty substrings such that each character of 'S' should present in exactly one substring.
2. Create a new string by concatenating 1st and 3rd parts.
Return 1 if you can make this new string a palindrome otherwise return 0.
For Example:-Let 'N' = 6, 'S' = "abccba".
Three substrings are "ab", "cc", and "ba" and by concatenating 1st and 3rd parts we get "abba" which is a palindrome.
So our answer is 1.
First-line contains an integer 'T', which denotes the number of test cases.
For every test case:-
First-line contains an integer 'N', denoting the length of the string 'S'.
Second-line contains a String 'S', which consists of 'N' lowercase English letters.
Output Format:-
For each test case, Return 1 if you can make this new string a palindrome otherwise return 0.
Note:-
You don’t need to print anything. Just implement the given function.
1 <= 'T' <= 10
3 <= 'N' <= 10^5
'S' consists of 'N' lowercase English letters.
The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
2
4
abcd
5
zzzzz
0
1
First test case:-
It can be proven that we cannot make the new string a palindrome.
So our answer is 0.
Second test case:-
Three substrings are "zzz", "z", and "z" and by concatenating 1st and 3rd parts we get "zzzz" which is a palindrome.
So our answer is 1.
2
4
abca
3
xyz
1
0
What can be the minimum size of the 1st and 3rd parts?
Approach:-
Algorithm:-
O(1)
We are taking constant time and the complexity associated with this is O(1). Hence, the overall time complexity is of the order O(1).
O(1)
We are using constant extra space, So the Space Complexity is O(1).