Katkat
Back

Check Whether a String Can Become a Palindrome by Deleting at Most One Character

WhatnotSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

A string coding problem that asks whether a lowercase string can be turned into a palindrome by deleting at most one character, returning a boolean. It tests careful handling of mismatched characters, strings that are already palindromes, and an efficient solution for strings of up to 100,000 characters.

Given a string s, return True if s can be made into a palindrome by deleting at most one character, and False otherwise. A palindrome reads the same forwards and backwards.

Function Signature

def can_be_palindrome_after_one_deletion(s: str) -> bool:

Rules

  • Deleting zero characters is allowed, so a string that is already a palindrome returns True.
  • At most one character may be deleted, from any position; the remaining characters keep their order.
  • A single character is a palindrome.

Constraints

  • 1 <= len(s) <= 10^5
  • s consists only of lowercase English letters a to z.

Examples

Example 1

Input: s = "abca"
Output: True

Deleting the c at index 2 gives "aba"; deleting the b at index 1 gives "aca".

Example 2

Input: s = "abcbaa"
Output: True

Deleting the a at index 4 gives "abcba".

Example 3

Input: s = "abc"
Output: False

"abc" is not a palindrome, and deleting one character leaves "bc", "ac" or "ab", none of which is.