Domain 1EasyCORE

Valid Palindrome II

The problem asks us to determine if a given string `s` can be transformed into a palindrome by deleting at most one character. A palindrome reads the same forwards and backwards.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

680. Valid Palindrome II

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 37.1%


Problem Breakdown

The problem asks us to determine if a given string s can be transformed into a palindrome by deleting at most one character. A palindrome reads the same forwards and backwards.

Inputs:

  • A non-empty string s containing only lowercase letters from ‘a’ to ‘z’.

Outputs:

  • A boolean value indicating whether it’s possible to make the string a palindrome by removing at most one character.

Implicit Constraints or Tricky Edge Cases:

  • The string length can be up to 50,000 characters.
  • The string is guaranteed to contain only lowercase letters, so we don’t need to handle other types of characters.
  • An empty string is not a valid input according to the problem statement.

Intuition

A brute-force approach would involve checking all possible substrings obtained by removing one character at a time and verifying if each substring is a palindrome. This approach has a time complexity of O(n^2) because we need to check each substring for being a palindrome, which takes linear time.

The key insight is that a string can be made into a palindrome by deleting at most one character if, when traversing the string from both ends towards the center, we encounter at most one mismatch. If there’s more than one mismatch, it’s impossible to make the string a palindrome with just one deletion.

Approach

  1. Use two pointers, left starting at the beginning of the string and right starting at the end.
  2. Move both pointers towards each other while comparing characters at these positions.
  3. If characters at left and right match, continue moving the pointers inward.
  4. If they don’t match, check if either skipping the character at left or skipping the character at right results in a palindrome:
    • Check if the substring from left+1 to right is a palindrome.
    • Check if the substring from left to right-1 is a palindrome.
  5. If either of these substrings is a palindrome, return True.
  6. If more than one mismatch is found, return False.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We traverse the string at most twice (once for each potential deletion).
  • Space Complexity: O(1). We only use a constant amount of extra space for the pointers and variables.

Solution

def validPalindrome(s: str) -> bool:
    def is_palindrome(subs: str) -> bool:
        return subs == subs[::-1]
    
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            # Check by skipping either the left or the right character
            return is_palindrome(s[left:right]) or is_palindrome(s[left+1:right+1])
        left += 1
        right -= 1
    
    return True

Edge Cases Handled

  • Single Character String: A single character string is inherently a palindrome, so the function returns True.
  • Already Palindrome String: If the input string is already a palindrome, the function will return True without any modifications.
  • Two Characters String with One Mismatch: The function correctly identifies that one deletion can make it a palindrome.
  • Longest Possible Input (50,000 characters): The solution efficiently handles large strings within the given constraints.