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
scontaining 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
- Use two pointers,
leftstarting at the beginning of the string andrightstarting at the end. - Move both pointers towards each other while comparing characters at these positions.
- If characters at
leftandrightmatch, continue moving the pointers inward. - If they don’t match, check if either skipping the character at
leftor skipping the character atrightresults in a palindrome:- Check if the substring from
left+1torightis a palindrome. - Check if the substring from
lefttoright-1is a palindrome.
- Check if the substring from
- If either of these substrings is a palindrome, return
True. - 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
Truewithout 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.