Check near-palindrome with one deletion
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a string s, determine whether it can become a palindrome after deleting at most one character. Return both the boolean result and one valid index to delete if possible. Provide an O(n) two-pointer solution and discuss how you would handle Unicode or case-insensitive comparisons.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Check near-palindrome with one deletion states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given a string `s`, determine whether it can become a palindrome after deleting **at most one** character.
Return a pair `[result, index]`:
- `result` is a boolean: `true` if `s` is already a palindrome or can be made one by deleting a single character, otherwise `false`.
- `index` is one valid 0-based index you could delete to make `s` a palindrome. If `s` is already a palindrome (no deletion needed) or no single deletion works, return `-1` for the index.
Use the classic two-pointer scan: walk inward from both ends; on the first mismatch, the only two candidates are deleting the left or the right character, so check whether either resulting substring is a palindrome. This runs in O(n) time and O(1) extra space.
Follow-up to discuss (not graded here): for Unicode you should normalize (e.g. NFC) and iterate over code points / grapheme clusters rather than UTF-16 code units; for case-insensitive comparison, casefold the string first — both are preprocessing steps that keep the core two-pointer logic unchanged.
Constraints
- 0 <= len(s) <= 10^5
- s consists of lowercase (or arbitrary) characters
- An empty string and a single-character string are palindromes (return [True, -1])
- If s is already a palindrome, the deletion index is -1 (no deletion needed)
Examples
Input: ("aba",)
Expected Output: [True, -1]
Explanation: Already a palindrome, so no deletion is needed; index is -1.
Input: ("abca",)
Expected Output: [True, 1]
Explanation: First mismatch at b vs c; deleting index 1 ('b') leaves 'aca', a palindrome.
Hints
- Use two pointers from both ends. As long as characters match, move inward.
- At the first mismatch, only two repairs are possible: delete the left character or delete the right one. Check if either remaining substring is a palindrome.
- If you reach the middle with no mismatch, the string was already a palindrome — return -1 for the index. If both repair attempts fail, it's impossible.