Grokking the Engineering Manager Coding Interview

0% completed

​

Valid Palindrome II (easy)

Problem Statement

Given string s, determine whether it's possible to make a given string palindrome by removing at most one character.

A palindrome is a word or phrase that reads the same backward as forward.

Examples

  1. Example 1:

    • Input: "racecar"
    • Expected Output: true
    • Justification: The string is already a palindrome, so no removals are needed.

  2. Example 2:

    • Input: "abccdba"
    • Expected Output: true
    • Justification: Removing the character 'd' forms the palindrome "abccba".

  3. Example 3:

    • Input: "abcdef"
    • Expected Output:

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
    def isPalindromePossible(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        count = 0
        while i < j:
            if count > 1:
                return False
            if s[i] == s[j]:
                i += 1
                j -= 1
            else:
                if s[i + 1] == s[j]:
                    i += 1
                elif s[j - 1] == s[i]:
                    j -= 1
                else:
                    return False
                count += 1
        return True
Show 1 reply
Ashish Karhade

Ashish Karhade

· 2 years ago

Solution is giving TLE. Why?

Show 1 reply
Ayush Kumar

Ayush Kumar

· 5 months ago

class Solution {
public:
    static bool isPalin(string s, int i, int j) {

        while (i < j) {
            if (s[i] != s[j])
                return false;
            i++;
            j--;    
        }
        return true;
    }
    bool validPalindrome(string s) {
        int i = 0, j = s.length() - 1;
        bool used = false;
        while (i < j) {
            if (s[i] != s[j]) {

                return isPalin(s, i + 1, j) || isPalin(s, i, j - 1);

            } else {
                i++;
                j--;
            }
        }
        return true;
    }
};