Mirror After One Cut

EasyTries & Strings

Problem

A typist may have pressed one extra key. Given a string s, return true if it is a palindrome or can become one by deleting at most one character.

Example 1

Input:
s = "racecxar"
Output:
true

Deleting the x gives "racecar".

Example 2

Input:
s = "abcd"
Output:
false

Example 3

Input:
s = "level"
Output:
true

Already a palindrome, no deletion needed.

Constraints

  • 1 ≤ s.length ≤ 10^5
  • Lowercase English letters only.

Hint

Show the first hint

Compare from both ends as for a normal palindrome. What should happen at the first mismatch?

Walkthrough

How to approach it

01Clarify before coding

  • Is deleting zero characters allowed? Yes, a palindrome is already valid.
  • Exactly one deletion at most, anywhere? Yes.
  • Case or punctuation issues? No, only lowercase letters.

02Brute force

Try deleting each of the n characters and test the result for being a palindrome.

Cost: O(n²): 10^5 deletions, each followed by an O(n) check.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.