Last Updated: 23 Oct, 2021
Valid Pallindrome ll
Easy
Asked in companies
Ninja’s friend challenged him with a trick question. He gave him a string ‘S’ and asked him if it is possible to make this string palindrome by deleting one character from the string. Can you help the ninja to solve this problem?
You are given a string ‘S’ of size ‘N’.You have to determine whether it is possible to make the string palindrome by deleting at most one character.
For Example
If the string is ‘AZBCDCBA’, the answer will be YES as we can delete the character ‘Z’ and the remaining string is a palindrome.
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 has a single integer ‘N’ denoting the length of string ‘S’.
The second line of each test case contains the string ‘S’.
Output Format:
For each test case, print ‘YES’ or ‘NO’ as is it possible to make the string palindrome by deleting at most one character.
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^5.
Time limit: 1 sec
Approaches
In this approach, we will first define a function IS_PALINDROME(‘S’, i,j), which returns whether the substring from i to j is palindrome or not. Now, we will take two pointers, i and j, and iterate the string using these pointers, one from the front and another from the back, when we find a condition that S[i] is not equal to S[j]. We have two choices:
Delete ith character. If substring from i+1 to j is a palindrome, the answer is true.
Delete jth character. If substring from i to j-1 is a palindrome, the answer is true.
If neither is true, we cant make this string palindrome. So return false.
If we never encounter the above condition, it means that our string is already palindrome. So, return simply true.
Algorithm:
- Defining IS_PALINDROME(‘S’, i,j) function, which will return if the substring from index i to j is palindromic or not:
- While i is less than j, do the following:
- If S[i] is not equal to S[j]:
- Return False.
- Set i as i+1.
- Set j as j-1.
- If S[i] is not equal to S[j]:
- Return True.
- While i is less than j, do the following:
- Declare two pointers i and j.
- Set i to 0 and j to ‘N’-1.
- While i is less than j, do the following:
- If S[i] is not equal to S[j]:
- We have two options to delete ith character or jth character.
- Return IS_PALINDROME(‘S’,i+1,j) OR IS_PALINDROME(‘S’,i,j-1).
- Set i as i+1.
- Set j as j-1.
- If S[i] is not equal to S[j]:
- If the While loop is terminated, it implies that the given string is already palindrome.
- Return True.