Valid Pallindrome ll

Easy
0/40
profile
Contributed by
17 upvotes
Asked in companies
FacebookAmazonGoogle

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
8
AZBCDCBA
3
ABA
Sample Output 1:
YES
YES
Explanation of sample input 1:
For the first test case,
If we remove the letter ‘Z’ from the string , the remaining string ‘ABCDCBA’ is palindromic.Hence, the answer is YES.

For the second test case:
The given string is already palindromic. Hence, the answer is YES.
Sample Input 2:
2
6
ROSSVR
6
VWHGWV
Sample Output 2:
NO
YES
Hint

Try out to find the character which does not match the condition of the palindrome.

Approaches (1)
Two Pointers Approach.

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.
    • Return True.
  • 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 the While loop is terminated, it implies that the given string is already palindrome.
  • Return True.
Time Complexity

O(N), where ‘N’ is the length of the string.

 

In this approach, we are iterating all characters of strings using two pointers. Hence, the overall time complexity is O(N).

Space Complexity

O(1).

 

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Valid Pallindrome ll
Full screen
Console