How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Palindrome After Deleting at Most One Character

Quick Overview

This question evaluates a candidate's ability to reason about two-pointer string traversal and palindrome verification under a single edit constraint. It tests practical application of algorithmic thinking on strings, a staple of coding interviews for assessing efficient linear-time problem solving with constant extra space.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A string is a **palindrome** if it reads the same forwards and backwards (for example, `"abccba"` and `"racecar"`). You are given a string `s` consisting only of lowercase English letters. You are allowed to delete **at most one** character from `s` (you may also delete nothing). Determine whether it is possible to make `s` a palindrome by performing at most one such deletion. Return `true` if `s` can become a palindrome after deleting at most one character, and `false` otherwise. ### Examples Example 1: - `s = "aba"` - Output: `true` - Explanation: `"aba"` is already a palindrome; no deletion is needed. Example 2: - `s = "abca"` - Output: `true` - Explanation: Deleting `'c'` (or `'b'`) yields `"aba"` (or `"aca"`), which is a palindrome. Example 3: - `s = "abcdef"` - Output: `false` - Explanation: No single deletion can make this a palindrome. ### Constraints - `1 <= s.length <= 10^5` - `s` consists only of lowercase English letters. A single character (and the empty string) is trivially a palindrome. Aim for `O(n)` time and `O(1)` extra space.

Quick Answer: This question evaluates a candidate's ability to reason about two-pointer string traversal and palindrome verification under a single edit constraint. It tests practical application of algorithmic thinking on strings, a staple of coding interviews for assessing efficient linear-time problem solving with constant extra space.

A string is a palindrome if it reads the same forwards and backwards (for example, "abccba" and "racecar"). You are given a string `s` consisting only of lowercase English letters. You are allowed to delete at most one character from `s` (you may also delete nothing). Determine whether it is possible to make `s` a palindrome by performing at most one such deletion. Return `true` if `s` can become a palindrome after deleting at most one character, and `false` otherwise. Examples: - s = "aba" -> true (already a palindrome) - s = "abca" -> true (delete 'c' or 'b') - s = "abcdef" -> false Constraints: - 1 <= s.length <= 10^5 - s consists only of lowercase English letters. Aim for O(n) time and O(1) extra space.

Constraints

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

Examples

Input: "aba"

Expected Output: true

Explanation: Already a palindrome; no deletion needed.

Input: "abca"

Expected Output: true

Explanation: Delete 'c' to get "aba" (or 'b' to get "aca").

Input: "abcdef"

Expected Output: false

Explanation: No single deletion can make it a palindrome.

Input: ""

Expected Output: true

Explanation: The empty string is trivially a palindrome.

Input: "a"

Expected Output: true

Explanation: A single character is trivially a palindrome.

Input: "deeee"

Expected Output: true

Explanation: Delete the leading 'd' to get "eeee", a palindrome.

Input: "ebcbbececabbacecbbcbe"

Expected Output: true

Explanation: Mismatch at the 'e'/'c' pair; skipping that one character leaves a palindrome.

Input: "abc"

Expected Output: false

Explanation: Deleting any one character still leaves a non-palindrome.

Input: "cbbcc"

Expected Output: true

Explanation: Delete the trailing 'c' to get "cbbc", a palindrome.

Input: "racecar"

Expected Output: true

Explanation: Already a palindrome.

Hints

Use two pointers, one at each end, moving inward while the characters match.
When you hit the first mismatch, you have exactly one deletion to spend: it must remove either the left or the right character.
Check whether the substring after skipping the left character is a palindrome, OR the substring after skipping the right character is a palindrome. If either holds, the answer is true.
A string of length 0 or 1 is trivially a palindrome.

Quick Overview