7.Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Examples
Input: "A man, a plan, a canal: Panama"
Output: true

Input: "race a car"
Output: false

Solution:-

class Solution {
public:
    bool isPalindrome(string s) {
        
        if(s==""){return true;}
        
       int start = 0;
       int end = s.length()-1;
        bool res = true;
       while(start<=end){
           
           int x = tolower(s[start]);
           int y = tolower(s[end]);
           if(x<97||x>122){
               if(x<48||x>57){
               start++;
               continue;
             }
           }
           
            if(y<97||y>122){
              if(y<48||y>57){
                end--;
                continue;
           }
          }
           
           if(x!=y){
                res = false;
                 break;
            }
    
           start++;
           end--;
       }
        
    return res;
    }
};

Time Complexity :- O(n)

Valid Palindrome II:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:
Input: "aba"
Output: True

Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Solution:

Algorithm: We will be comparing char from start and end. If there is a mismatch. Then we can make one deletion We will make one deletion and check and if the rest is string is palindrome.

class Solution
{
public:
    bool isPallen(string s, int start, int end)
    {
        while (start < end)
        {
            if (s[start] != s[end])
            {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    bool validPalindrome(string s)
    {
        int start = 0;
        int end = s.length() - 1;

        while (start < end)
        {
            if (s[start] != s[end])
            {
                if (isPallen(s, start + 1, end) || isPallen(s, start, end - 1))
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            start++;
            end--;
        }
        return true;
    }
};