Home » Technical Interview Questions » String Interview Questions » Valid Palindrome

# Valid Palindrome

Given a string s of length n. Write a program to find if the string is valid palindrome or not. If not you may delete at most one character from the string to make it a palindrome.

Any string which is the same as it’s reverse is known as a palindrome.

For example:

1. string = “nitin” and reverse string = “nitin” which are the same therefore it is a palindrome.
2. string = “apple” and reverse string = “elppa” which are not the same therefore it is not a palindrome. ## Example

Input : s = “abcdba”

Output: Yes     (by removing either ‘c’ or ‘d’)

Input : s = “abba”

Input : s = “blue”

Output: No

## Algorithm for Valid Palindrome

Now we understand the problem statement in simplest way. So, now for the implementation part move to the algorithm used for implementation.

1. Initialize a string.
2. Start traversing using the starting index and ending index pointer.
3. Check if the character at both indexes is equal increment starting pointer and decrement ending pointer. If starting index is greater than or equal to ending index return true.
4. Else try making palindrome by removing one of these characters.
5. If removing the character at starting index results in palindrome return true.
6. Else if removing the character at ending index results in palindrome return true.
7. Else return false.

## C++ Program to check Valid Palindrome

```#include <bits/stdc++.h>
using namespace std;

bool isPalindrome(string::iterator low, string::iterator high){
while(low < high){
if(*low != *high)
return false;
low++;
high--;
}
return true;
}

bool Palindrome(string s){
int low = 0, high = s.length() - 1;

while(low < high){
if(s[low] == s[high]){
low++;
high--;
}
else{
if(isPalindrome(s.begin() + low + 1, s.begin() + high))
return true;

if (isPalindrome(s.begin() + low, s.begin() + high - 1))
return true;

return false;
}
}

return true;
}

int main(){
string s = "abcdba";

if(Palindrome(s)){
cout<<"Yes";
}
else{
cout<<"No";
}
return 0;
}```
`Yes`

## Java Program to check Valid Palindrome

```import java.util.*;

class validPalindrome{

static boolean isPalindrome(String s, int low, int high){
while(low < high){
if(s.charAt(low) != s.charAt(high))
return false;
low++;
high--;
}
return true;
}

static boolean Palindrome(String s){

int low = 0, high = s.length() - 1;

while(low < high){

if(s.charAt(low) == s.charAt(high)){
low++;
high--;
}
else{

if(isPalindrome(s, low + 1, high))
return true;

if(isPalindrome(s, low, high - 1))
return true;
return false;
}
}

return true;
}

public static void main(String[] args){
String s = "abcdba";

if(Palindrome(s)){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
```
`Yes`

## Complexity Analysis

### Time Complexity

O(n)  where n is the length of the given string.

READ  Substring With Concatenation Of All Words

### Auxiliary Space

O(1) because we don’t use any extra space here.

Refrences

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions 