Practice/Microsoft/Leetcode 680. Valid Palindrome II

Leetcode 680. Valid Palindrome II

CodingMust

Problem

Given a string, determine if it can be transformed into a palindrome by removing at most one character from it.

A palindrome is a string that reads the same forward and backward. Your task is to check whether the input string is already a palindrome, or if removing exactly one character would make it a palindrome.

Requirements

1. Return true if the string is already a palindrome or can become one by deleting at most one character
2. Return false if removing one character cannot make it a palindrome
3. The comparison should be case-sensitive
4. Only consider removing exactly zero or one character (not more)

Constraints

• 1 ≤ length of string ≤ 100,000
• The string consists of lowercase English letters only
• Aim for O(n) time complexity where n is the length of the string
• Aim for O(1) space complexity (not counting the input)

Examples

Example 1:

Input: s = "racecar" Output: true Explanation: The string is already a palindrome without any deletions.

Example 2:

Input: s = "abca" Output: true Explanation: We can remove 'b' to get "aca" (a palindrome) or remove 'c' to get "aba" (also a palindrome).

Example 3:

Input: s = "abcdef" Output: false Explanation: No single character removal can turn this into a palindrome.

Example 4:

Input: s = "ab" Output: true Explanation: Removing either 'a' or 'b' leaves a single character, which is trivially a palindrome.