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”

Output: Yes     (already a palindrome)

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.

Auxiliary Space

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

Refrences