How to Check if a String Can Be a Palindrome After Removing One Character

How to Check if a String Can Be a Palindrome After Removing One Character

At Python Haven, we specialize in helping you master complex algorithms through simple, practical explanations. 

Today, we'll guide you step-by-step through a classic problem: 

"Can a string become a palindrome after removing at most one character?"

You're in the right place if you're preparing for coding interviews, system design, or just strengthening your algorithm muscles.

Let’s walk through it cleanly and professionally, with optimized code, helpful comments, and simple logic that even a 2-year-old could grasp.

What Is the Problem?

First, understand the question clearly:

You are given a string.

-> Your task: Check if it’s possible to make it a palindrome by removing at most one character.

Example:

"abca"  -> Yes (remove b or c to get "aca" or "aba")
"abc"  ->  No (even after removing one letter, not a palindrome)

Before presenting the optimized code, here's my unoptimized one. Make a comparison later to understand why the latter solution is better!

In fact, in the first unoptimized solution, only the first four tests complete while the rest "hang" -> it is like nothing is happening!

Unoptimized Solution 1

def is_valid_palindrome(s: str) -> bool:
    # Use a while loop to compare characters from both ends
    for i in range(len(s) // 2):
        if s[i] != s[-(i + 1)]:
            return False
    return True
        

def valid_palindrome_ii(s: str)->bool:
    "Given a string, return true if it can be a palindrome after removing at most one character"
    for i in range(len(s)):
        new_s=s[:i]+s[i+1:]
        if is_valid_palindrome(new_s):
            return True
    return False


print(f"Expected: True, Actual:", valid_palindrome_ii("abca")) # True (remove 'b' or 'c')
print(f"Expected: False, Actual:", valid_palindrome_ii("abc")) # False (can't fix with one removal)
print(f"Expected: True, Actual:", valid_palindrome_ii("deeee")) # True (remove 'd')
print(f"Expected: True, Actual:", valid_palindrome_ii("racecar"))
print(f"Expected: True, Actual:", valid_palindrome_ii("a"*50000 + "b" + "a"*50000))
print(f"Expected: False, Actual:", valid_palindrome_ii("a"*50000 + "b"*50000))

Unoptimized Solution 2

def is_valid_palindrome(s:str)->bool:
    i,j =0, len(s)-1
    while i < j:
        if s[i] != s[j]:
            return False
        else:
            i +=1
            j -=1
    return True

def valid_palindrome_ii(s: str)->bool:
    "Given a string, return true if it can be a palindrome after removing at most one character"
    l = 0
    r = len(s)-1
    while l < len(s):
        if s[l] != s[r]:
            return is_valid_palindrome(s[l+1:]) or is_valid_palindrome(s[l:r])
        l +=1
        r -=1
    return True


print(f"Expected: True, Actual:",  valid_palindrome_ii("abca")) # True (remove 'b' or 'c')
print(f"Expected: False, Actual:", valid_palindrome_ii("abc")) # False (can't fix with one removal)
print(f"Expected: True, Actual:",  valid_palindrome_ii("deeee")) # True (remove 'd')
print(f"Expected: True, Actual:",  valid_palindrome_ii("racecar"))
print(f"Expected: True, Actual:",  valid_palindrome_ii("a"*50000 + "b" + "a"*50000))
print(f"Expected: False, Actual:", valid_palindrome_ii("a"*50000 + "b"*50000))

Clean Code Implementation (Explained Step-by-Step)

Let’s now break down the code you need — clean, optimized, and easy to understand.

Here’s the full code first:

def is_valid_palindrome(s: str, left: int, right: int) -> bool:
    """
    Helper function to check if the substring s[left:right+1] is a valid palindrome.
    
    Args:
        s (str): The input string.
        left (int): Starting index of the substring.
        right (int): Ending index of the substring.
        
    Returns:
        bool: True if the substring is a palindrome, False otherwise.
    """
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

def valid_palindrome_ii(s: str) -> bool:
    """
    Check if the input string can become a palindrome by removing at most one character.
    
    Args:
        s (str): The input string.
        
    Returns:
        bool: True if the string can be a palindrome after at most one removal, False otherwise.
    """
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # Try skipping either the left or the right character
            return is_valid_palindrome(s, left + 1, right) or is_valid_palindrome(s, left, right - 1)
        left += 1
        right -= 1
    return True

Step-by-Step Explanation

Step 1: Understand What a Palindrome Is

A palindrome is a word or sentence that reads the same forward and backward.

Example: "madam", "racecar".

Imagine pointing two fingers at the start and end of the word and moving them toward each other.

If letters match all the way — it's a palindrome!

Step 2: Create a Helper Function

We make a small tool — called is_valid_palindrome() — that checks any part of the string to see if it's a palindrome.

It looks at two sides (left and right).

• If characters don't match:  return False.
• If all characters match:  return True.

Key Optimization

Instead of cutting the string (which costs memory), we use indexes to move inside the string.

This saves time and memory — crucial for coding interviews.

Step 3: Create the Main Function

The main function valid_palindrome_ii(s) does the heavy lifting:

• Start two fingers, one at each end (left and right).
• Walk toward each other.
• If letters match: move inward.

If letters don't match:

• Try skipping one letter from the left.
• OR try skipping one letter from the right.
• If either works ->  the string is valid.
• If you reach the middle and everything matches ->  the original string was already a palindrome.

Code Behavior Illustration

Here’s a simple visualization of how the code works:

String                                                          Action                                                                                                Result
 "abca"          'a' == 'a' ->  move in. 'b' != 'c' -> skip 'b' or 'c' and check.                                                           True    
"abc"             'a' != 'c' ->   skip 'a' or 'c', neither "bc" nor "ab" is a palindrome.                                               False    
"deeee"        'd' != 'e' ->  skip 'd', "eeee" is a palindrome.                                                                                  True    

Why This Code Is Perfectly Optimized

• No slicing strings (no memory wastage)
• Constant time character checks (O(1))
• Linear time traversal (O(n))
• Straightforward to debug and extend (only two functions, clearly separated)

You get a highly efficient solution suitable for real-world production, coding interviews, and large input sizes.

How to Level Up from Here

Now that you understand how to check if a string can be a palindrome after removing at most one character, try the following to get even better:

1. Extend the code to allow removing up to two characters.
2. Practice similar problems like the Longest Palindromic Substring.
3. Try implementing the same solution using recursion instead of iteration.
4. Every small problem you master, like this one, moves you closer to becoming an elite problem-solver.

Ready to Build Even More Powerful String Algorithms?

You now have a clean, professional-grade, highly optimized solution to the valid palindrome II problem. If you enjoyed this, check out more algorithm tutorials at Python Haven and keep growing your coding superpowers.

Dive deeper, code smarter, and stay sharp — your future self will thank you.