Palindrome After Deleting At Most One Character

Easy15–20 min

Topics

StringTwo Pointer

Companies

AmazonGoogleFacebookAdobe

Given a string s, return true if it can become a palindrome by deleting at most one character. Walking two pointers inward from both ends handles the matching characters for free. The only real decision point is the first mismatch: since only one deletion is allowed, there are exactly two ways to fix it — drop the character at the left pointer, or drop the one at the right pointer. Whichever choice leaves a palindrome in the remaining range makes the answer true. Checking both candidate ranges still keeps the whole algorithm at O(n), since every character is visited only a small, constant number of times.

Test Case 1:

Input:s = "abbca"

Output:true

Explanation:Removing the 'c' at index 3 leaves "abba", which is a palindrome.

Test Case 2:

Input:s = "abc"

Output:false

Explanation:No single removal makes the remaining string a palindrome.

Test Case 3:

Input:s = "aba"

Output:true

Explanation:The string is already a palindrome, so zero removals are needed.

Constraints

◆1 ≤ s.length ≤ 10⁵
◆s consists of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (lowercase) — 3-10 lowercase letters

1	class Solution {
2	public boolean canBeAPalindromeAfterOneRemoval(String s) {
3	int left = 0, right = s.length() - 1;
4	while (left < right) {
5	if (s.charAt(left) != s.charAt(right)) {
6	boolean skipLeft = isPalindromeRange(s, left + 1, right);
7	boolean skipRight = isPalindromeRange(s, left, right - 1);
8	return skipLeft \|\| skipRight;
9	}
10	left++;
11	right--;
12	}
13	return true;
14	}
15	private boolean isPalindromeRange(String s, int left, int right) {
16	while (left < right) {
17	if (s.charAt(left) != s.charAt(right)) return false;
18	left++;
19	right--;
20	}
21	return true;
22	}
23	}
24

↑left

↑right

Variables

left0

right4

INITIALIZE

Set left to 0 and right to the last index, 4. Move them toward each other until a mismatch appears.

Step 1 / 6

Approach & Solutions

Brute Force

Brute

Try removing each index in turn, building the string that remains, and check whether that shorter string is a palindrome. If any single removal produces a palindrome, the answer is true. Correct, but it rebuilds and re-checks a whole new string for every one of the n possible removals.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean canBeAPalindromeAfterOneRemoval(String s) {
        int n = s.length();
        for (int i = 0; i < n; i++) {
            String candidate = s.substring(0, i) + s.substring(i + 1);
            boolean ok = true;
            int left = 0, right = candidate.length() - 1;
            while (left < right) {
                if (candidate.charAt(left) != candidate.charAt(right)) { ok = false; break; }
                left++;
                right--;
            }
            if (ok) return true;
        }
        return false;
    }
}

Optimal — Two Pointers

Optimal

Walk two pointers inward from both ends. While characters match, keep moving inward — that costs nothing extra. The moment a mismatch appears, there are only two possible fixes: skip the left character, or skip the right one. Check whether the remaining range is a palindrome under either choice; if either works, the answer is true. Each character is visited a small, constant number of times, so the whole check runs in O(n).

TimeO(n)

SpaceO(1)