Greedy: Check if a given string becomes palindrome by deleting atmost one char

Problem Statement:

You are given a string and you need to return true if the string is palindrome, by deleting at most one character.

Example:

Input: s = "abda"
Output: True

Delete d and the string will become palindrome

Solution Explanation:

We will use greedy approach to solve the problem.

Take 2 pointers, left and right.

If the char match, continue inward, if mismatch occurs, we remove one character either left or right and come to the solution.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

bool isPalindrome(string& s, int left, int right) 
{
    while (left < right) 
    {
        if (s[left] != s[right]) 
        	return false;

        left++;
        right--;
    }

    return true;
}


bool solution(string s) 
{
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) 
    {
        if (s[left] != s[right]) 
        {
            return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
        }

        left++;
        right--;
    }
    return true;
}

int main() 
{
    string s = "aba";
    if (solution(s))
    	cout <<"True";
    else
    	cout<<"False";
    	
    return 0;
}

Output

True