Show problems as
Classic problem #680EasyTwo PointersStringGreedy

Valid Palindrome II

Real-world version: Mosaic Border Inspection
Tracked in this browser only
Read Valid Palindrome II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A mosaic studio finishes decorative border strips before they ship. A strip arrives as the string strip, one lowercase letter per tile naming that tile's glaze, listed from the left end of the strip to the right end.

The studio accepts a strip when it shows the same glaze sequence read from either end, and the finisher is allowed to pull out at most one tile first. Pulling a tile out closes the gap, so the two tiles that flanked it become neighbours. Pulling nothing out is also allowed, so a strip that already matches end to end is accepted as it stands.

Return true when the strip can be accepted and false when no single removal is enough.

Examples

Example 1

Input
strip = "levels"
Output
true

Pull the trailing `s` and the remaining six-tile run `level` shows the same glazes from either end.

Example 2

Input
strip = "cobalt"
Output
false

Dropping the `c` still leaves `obalt` mismatched at its ends, and dropping the `t` leaves `cobal` mismatched too, so one removal cannot rescue it.

Example 3

Input
strip = "kayak"
Output
true

The strip already matches end to end, and removing nothing is permitted.

Constraints

  • 1 <= strip.length <= 10^5
  • strip consists of lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def inspect_border(strip: str) -> bool:
Java
public boolean inspectBorder(String strip)

More on the same topics