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.

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

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

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup