Check Whether a String Can Become a Palindrome by Deleting at Most One Character
Company: Whatnot
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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
```python
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**
```text
Input: s = "abca"
Output: True
```
Deleting the `c` at index 2 gives `"aba"`; deleting the `b` at index 1 gives `"aca"`.
**Example 2**
```text
Input: s = "abcbaa"
Output: True
```
Deleting the `a` at index 4 gives `"abcba"`.
**Example 3**
```text
Input: s = "abc"
Output: False
```
`"abc"` is not a palindrome, and deleting one character leaves `"bc"`, `"ac"` or `"ab"`, none of which is.
Overview: 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.
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.
The function returns a boolean (`True`/`False` in Python, `true`/`false` in JavaScript, Java and C++). The only input is the string `s`; no value in this problem can exceed 2^31 - 1, so 32-bit integers suffice for indices in every language.
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 = "abc"
Output: False
"abc" is not a palindrome, and deleting one character leaves "bc", "ac" or "ab", none of which is.
Constraints:
- 1 <= len(s) <= 10^5
- s consists only of lowercase English letters 'a' to 'z'.
Constraints
- 1 <= len(s) <= 10^5
- s consists only of lowercase English letters 'a' to 'z'.
Examples
Input: ('a',)
Expected Output: True
Explanation: Minimum length 1: a single character is a palindrome, zero deletions.
Input: ('aa',)
Expected Output: True
Explanation: Length 2, equal letters: already a palindrome.
Hints
- Deleting zero characters is allowed, and a one-character string is already a palindrome, so start by asking when no deletion is needed at all.
- If the first and last characters are equal, ask whether either of them ever needs to be the deleted character, and what that says about the inner part of the string.
- Test your idea on abcbaa (the character to delete sits near the end) and on abc (no single deletion works).