Katkat
Back

Palindrome After Deleting at Most One Character

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize string traversal using a two-pointer approach, specifically handling conditional branch logic when an inconsistency is detected.

Problem Statement

Given a string s, return true if the string can become a palindrome after removing at most one character from it. Otherwise, return false.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.

Examples

Example 1: Input: s = "aba" Output: true Explanation: Already a palindrome.

Example 2: Input: s = "abca" Output: true Explanation: You could delete the character 'b' or 'c'.

Example 3: Input: s = "abc" Output: false Explanation: Deleting any character results in a non-palindrome.

Function Signature

def validPalindrome(s: str) -> bool:

Edge Cases

  • Empty strings or single-character strings (always palindromes).
  • Strings where the mismatch occurs at the very beginning or end.
  • Strings where multiple deletions would be required.

Hints

Hint 1

Use two pointers, one starting at the beginning and one at the end, moving towards the center while characters match.

Hint 2

When a mismatch occurs, you have two choices: skip the character at the left pointer or skip the character at the right pointer.

Hint 3

If skipping either one results in a valid palindrome, the function should return true.

Follow-up questions

  • How would you modify your solution if you were allowed to delete up to 'k' characters?
  • Can you solve this problem in O(n) time and O(1) space?
  • What would the complexity look like if you needed to return the actual characters removed?