1-3 Palindrome

Easy
0/40
Average time to solve is 5m
profile
Contributed by
8 upvotes
Asked in company
British Telecommunications

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:-
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.
Constraints:-
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
Sample Input 1:-
2
4
abcd
5
zzzzz   
Sample Output 1:-
0
1
Explanation of sample input 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.
Sample Input 2:-
2
4
abca
3
xyz

Sample Output 2:-

1
0
Hint

What can be the minimum size of the 1st and 3rd parts?

Approaches (1)
Conditionals Approach

Approach:-

 

  • We split the string in such a manner that 1st part only contains the first character, 3rd part only contains the last character, and 2nd part contains characters from index 2 to 'N' - 1.
  • So to check for the palindrome, We just have to check whether the first and last character of the string is equal or not.
     

 Algorithm:-
 

  • If(S[1] == S[N]):
    • Return 1.
  • Else:
    • Return 0.
Time Complexity

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

Space Complexity

O(1)

 

We are using constant extra space, So the Space Complexity is O(1).

Code Solution
(100% EXP penalty)
1-3 Palindrome
Full screen
Console