Loading…

easyStrings0Frequently asked

Palindrome Index

Q: How do you solve Palindrome Index using the Try Removing Each Index (Brute Force) approach?

When to use it: State it to anchor correctness, then note it's O(n²) and that two pointers find the suspect directly. Literally enumerate the answer: for each index `i`, delete it and test the result for palindromicity. Return the first index that produces a palindrome; if none is needed, return −1. **Why it's correct.** The answer is by definition 'some index whose removal yields a palindrome'. Trying them all cannot miss it, and the first hit is a valid answer (the problem accepts any). **Why we improve it.** Two pointers reveal the *only* indices worth trying. Everywhere the ends already match, deleting an interior matched character can't fix anything (the mismatch is elsewhere). So the entire search collapses to the first mismatch position and its mirror — two candidates, one re-check — instead of `n` full checks. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Palindrome Index using the Two Pointers with One-Side Re-check (Optimal) approach?

When to use it: The intended answer — converge from the ends, and at the first mismatch run a single inner palindrome test to pick the side. Set `l = 0`, `r = n − 1`. While `s[l] == s[r]`, advance `l++`, `r--`. If the loop finishes, `s` is already a palindrome → return −1. At the first mismatch, the two suspects are `s[l]` and `s[r]`. Run one targeted check: is `s[l+1 .. r]` a palindrome (i.e. would removing the left character fix it)? If yes, return `l`. Otherwise the only remaining possibility — guaranteed by the problem — is that removing the right character works, so return `r`. **Why only two candidates exist.** Every step before the mismatch confirmed `s[l] == s[r]`, a symmetric matched layer. Deleting a character inside a matched layer can't repair a break that lives deeper in; it would only desynchronise the symmetry. So the break must be healed at the boundary where it appears — by dropping `s[l]` or `s[r]`. **Why one re-check suffices.** The guarantee says some single deletion works. We test the 'skip left' range directly; if it's a palindrome we're done. If it isn't, we don't need to also verify 'skip right' — the guarantee forces it to be the answer. (You may verify it for safety, but it's logically implied.) **Why O(1) space.** The inner check uses indices `l+1` and `r`, walking inward with two more pointers — no substring is materialized. **Why this is O(n) not O(n²).** Unlike brute force, there is at most a single inner check, and it runs once at the unique first mismatch — not once per index. Time complexity: O(n). Space complexity: O(1).

Arrays & Hashing · 65 of 83 · 7 min

Given a string s, determine the index of a character that can be removed to make s a palindrome. There is always a valid solution: either the string is already a palindrome, or removing exactly one character makes it one.

If s is already a palindrome, return -1. Otherwise return the 0-based index of the character to remove. If multiple indices work, any valid one is acceptable.

In plain English

A palindrome reads the same forwards and backwards, so checking it is naturally a two-pointer walk from both ends. While the ends agree, the outer layer is symmetric and we peel inward. The moment they disagree, the culprit is one of those two mismatched characters. Because we're promised a one-deletion fix, removing the right suspect must turn the remaining string into a palindrome — we just have to figure out which suspect.

Examples

Example 1

Input: s = "aaab"
Output: 3
Note: l=0 'a' vs r=3 'b' mismatch. Is s[1..3]="aab" a palindrome? No. So remove right index 3 → "aaa" is a palindrome.

Example 2

Input: s = "baa"
Output: 0
Note: l=0 'b' vs r=2 'a' mismatch. Is s[1..2]="aa" a palindrome? Yes. So remove left index 0 → "aa" is a palindrome.

Example 3

Input: s = "aaa"
Output: -1
Note: Already a palindrome; pointers cross with no mismatch → −1.

Constraints

1 ≤ |s| ≤ 10⁵
s consists of lowercase English letters
A valid answer always exists (remove at most one character)
Return any valid index, or −1 if already a palindrome

Clarifying questions4First question: What if it's already a palindrome?Explore questions

Q1.What if it's already a palindrome?
Return −1 — no removal is needed. The two-pointer loop completes without a mismatch.
Q2.Is a solution guaranteed?
Yes. The problem promises that removing at most one character yields a palindrome, so after the first mismatch one of the two sides is guaranteed to work.
Q3.If two indices both work, which do I return?
Any valid index. For 'aba' style ties, returning either symmetric position is accepted.
Q4.Do I need to build the resulting palindrome?
No — only the index. The internal palindrome re-check uses index bounds, not new strings, to stay O(1) space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Walk two pointers from the ends inward. As long as s[left] == s[right], move in. At the first mismatch, exactly one of the two characters must go: test whether the inner substring s[left+1..right] is a palindrome — if so, remove left; otherwise remove right. If the pointers cross with no mismatch, the string is already a palindrome → return −1. O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for converging two pointers on a palindrome and handle the 'which side to remove' decision with a single targeted re-check rather than brute-forcing every deletion.

Where candidates slip

Returning the first mismatch index without verifying which side actually fixes the palindrome, or forgetting the −1 case when the string is already a palindrome.

How to stand out

Explain that at the first mismatch only two candidates exist (left or right), and one O(n) sub-check decides between them — so the whole thing stays O(n), not O(n²).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Try Removing Each Index (Brute Force)	`O(n²)`	`O(n)`	State it to anchor correctness, then note it's O(n²) and that two pointers find the suspect directly.	Read
2	Two Pointers with One-Side Re-check (Optimal)Optimal	`O(n)`	`O(1)`	The intended answer — converge from the ends, and at the first mismatch run a single inner palindrome test to pick the side.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewl=0, r=n-1s[l] == s[r]?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Try Removing Each Index (Brute Force)

TimeO(n²)SpaceO(n)

State it to anchor correctness, then note it's O(n²) and that two pointers find the suspect directly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some index i to delete. What's the most direct way to test a candidate?

2Hint 2Explore hint

For each i, form s with index i removed and check whether it's a palindrome.

3Hint 3Explore hint

Return the first i that works, or −1 if s is already a palindrome. Note this is n palindrome checks → O(n²).

A · Core idea

Literally enumerate the answer: for each index i, delete it and test the result for palindromicity. Return the first index that produces a palindrome; if none is needed, return −1.

Why it's correct. The answer is by definition 'some index whose removal yields a palindrome'. Trying them all cannot miss it, and the first hit is a valid answer (the problem accepts any).

Why we improve it. Two pointers reveal the only indices worth trying. Everywhere the ends already match, deleting an interior matched character can't fix anything (the mismatch is elsewhere). So the entire search collapses to the first mismatch position and its mirror — two candidates, one re-check — instead of n full checks.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "baa"

Array state

remove 0

"aa" → palindrome

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

Reference implementation previewpublic int palindromeIndex(String s) { if (isPalindrome(s, 0, s.length() - 1)) return -1; for (int i = 0; i < s.length(); i++) { String candidate = s.substring(0, i) + s.substring(i + 1); if (isPalindrome(candidate, 0, candidate.length() - 1)) return i;Explore the full code

solution.javaJava

Try Removing Each Index (Brute Force) — reference

3 teaching notes

1
public int palindromeIndex(String s) {
2
    // Already a palindrome → no deletion needed.
3
    if (isPalindrome(s, 0, s.length() - 1)) return -1;
4
    for (int i = 0; i < s.length(); i++) {
5
        // Build s with index i removed — O(n) per candidate.
6
        String candidate = s.substring(0, i) + s.substring(i + 1);
7
        if (isPalindrome(candidate, 0, candidate.length() - 1)) return i;
8
    }
9
    return -1;
10
}
11
 
12
private boolean isPalindrome(String s, int l, int r) {
13
    while (l < r) {
14
        if (s.charAt(l) != s.charAt(r)) return false;
15
        l++;
16
        r--;
17
    }
18
    return true;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

Brute force tests every index; the two-pointer scan proves only two indices can possibly be the answer. Recognising that the first asymmetry localizes the suspects is what removes the outer O(n) factor.

ComplexityO(n²) time, O(n) space — Up to n candidate indices, each requiring an O(n) palindrome check on a length-(n−1) string → O(n²) time; building each candidate string costs O(n) space.

E · Edge cases and pitfalls5s = "a" — Single char is a palindrome → −1.Explore edge cases

Edge cases handled

s = "a"Single char is a palindrome → −1.
s = "ab"Remove index 0 → "b" palindrome → returns 0.

Pitfalls

O(n²) is too slow for n = 10⁵.
Rebuilding strings repeatedly wastes O(n) memory per try.
Forgetting the already-palindrome → −1 short-circuit.

03.2

Approach 2 of 2 · Optimal

Two Pointers with One-Side Re-check (Optimal)

TimeO(n)SpaceO(1)

The intended answer — converge from the ends, and at the first mismatch run a single inner palindrome test to pick the side.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Checking a palindrome is a converging two-pointer walk. Where does that walk first break?

2Hint 2Explore hint

At the first l/r mismatch, the removable character is either s[l] or s[r] — nothing else.

3Hint 3Explore hint

Test whether skipping left (s[l+1..r]) is a palindrome: if yes return l, else return r. If the walk never breaks, return −1.

A · Core idea

Set l = 0, r = n − 1. While s[l] == s[r], advance l++, r--. If the loop finishes, s is already a palindrome → return −1.

At the first mismatch, the two suspects are s[l] and s[r]. Run one targeted check: is s[l+1 .. r] a palindrome (i.e. would removing the left character fix it)? If yes, return l. Otherwise the only remaining possibility — guaranteed by the problem — is that removing the right character works, so return r.

Why only two candidates exist. Every step before the mismatch confirmed s[l] == s[r], a symmetric matched layer. Deleting a character inside a matched layer can't repair a break that lives deeper in; it would only desynchronise the symmetry. So the break must be healed at the boundary where it appears — by dropping s[l] or s[r].

Why one re-check suffices. The guarantee says some single deletion works. We test the 'skip left' range directly; if it's a palindrome we're done. If it isn't, we don't need to also verify 'skip right' — the guarantee forces it to be the answer. (You may verify it for safety, but it's logically implied.)

Why O(1) space. The inner check uses indices l+1 and r, walking inward with two more pointers — no substring is materialized.

Why this is O(n) not O(n²). Unlike brute force, there is at most a single inner check, and it runs once at the unique first mismatch — not once per index.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aaab"

Array state

l=0,r=3

'a' vs 'b' → mismatch

l ↓

[0]

[1]

[2]

r ↓

[3]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Two Pointers with One-Side Re-check (Optimal) — optimal

5 teaching notes

1
public int palindromeIndex(String s) {
2
    int l = 0, r = s.length() - 1;
3
    // Converge from both ends — the palindrome check itself.
4
    while (l < r) {
5
        // First asymmetry: the answer is index l or r.
6
        if (s.charAt(l) != s.charAt(r)) {
7
            // Skipping left makes it a palindrome → remove left.
8
            if (isPalindrome(s, l + 1, r)) return l;
9
            // Otherwise the guaranteed fix is removing right.
10
            return r;
11
        }
12
        l++;
13
        r--;
14
    }
15
    // Loop finished with no mismatch → already a palindrome.
16
    return -1;
17
}
18
 
19
private boolean isPalindrome(String s, int l, int r) {
20
    while (l < r) {
21
        if (s.charAt(l) != s.charAt(r)) return false;
22
        l++;
23
        r--;
24
    }
25
    return true;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

A palindrome's first point of asymmetry is a chokepoint: it localizes all possible answers to two positions. This 'find the break, then branch on a local repair' shape recurs in Valid Palindrome II and many greedy-on-symmetry problems.

ComplexityO(n) time, O(1) space — The outer walk is one pass, O(n). At most one inner palindrome check over a sub-range, also O(n). Total O(n) time, O(1) space (index arithmetic only — no string copies).

E · Edge cases and pitfalls6s = "racecar" — Already a palindrome → loop completes → −1.Explore edge cases

Edge cases handled

s = "racecar"Already a palindrome → loop completes → −1.
s = "abca"Mismatch at l=1 'b' vs r=2 'c'. Skip left → "c" palindrome → return 1 (remove 'b').
s = "aaab"Skip-left "aab" not a palindrome → return r = 3.

Pitfalls

Returning the mismatch index without the inner re-check to pick the correct side.
Materializing substrings for the inner check instead of using index bounds (O(n) space).
Missing the −1 path when the string is already a palindrome.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int palindromeIndex(String s) { int l = 0, r = s.length() - 1; while (l < r) { if (s.charAt(l) != s.charAt(r)) { if (isPalindrome(s, l + 1, r)) return l;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Guessing the side at the mismatch

At the first mismatch either s[l] or s[r] could be the culprit. Returning l (or r) without a re-check is wrong half the time — e.g. 'aaab' needs r, 'baa' needs l.

Explore the code comparison

Don't write this

if s[l] != s[r]:
    return l   # blind guess

Write this instead

if s[l] != s[r]:
    return l if is_pal(l + 1, r) else r

Forgetting the already-palindrome case

If the loop never hits a mismatch the string is a palindrome and the answer is −1; falling through to return 0 (or l) is incorrect.

Explore the code comparison

Don't write this

while (l < r) { if (s.charAt(l) != s.charAt(r)) { ... } l++; r--; }
return 0;

Write this instead

while (l < r) { if (s.charAt(l) != s.charAt(r)) { ... } l++; r--; }
return -1;

Copying substrings for the inner check

Building s[l+1..r] as a new string costs O(n) memory and time on every call; pass index bounds instead to keep O(1) space.

Explore the code comparison

Don't write this

sub = s[l + 1:r + 1]
if sub == sub[::-1]: return l

Write this instead

if is_pal(l + 1, r): return l

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-pointer scan + one-side palindrome retest

Code pattern to memorize

l, r = 0, n-1
while l < r:
    if s[l] != s[r]:
        if isPalindrome(s, l+1, r): return l
        else: return r
    l++, r--
return -1

Rules to remember

1At the first mismatch the removable index is left or right — decide by retesting the narrowed range.
2Test s[l+1..r] (skip left): if it's a palindrome, removing left works → return l.
3Otherwise removing right must work (the problem guarantees a solution) → return r.
4No mismatch through the whole scan → already a palindrome → return −1.
5The guarantee 'removing at most one char makes it a palindrome' means you never need to test both deeply.

Use this pattern when

Symmetric (palindrome) property checked from both ends
You may remove exactly one element and must locate which
A single localized mismatch decides the answer
O(1) extra space is desired — pointers, no copies

Choose another pattern when

More than one deletion allowed → becomes a DP (longest palindromic subsequence)
Need the resulting string, not the index → build it after deciding
Insertions allowed instead of deletions → min-insertions DP
Case/space normalization required → preprocess first (Valid Palindrome II family)

Interview takeaway

Palindrome checks are two pointers converging from the ends. The first asymmetry pins down a single suspect on each side; retesting the range with one side skipped tells you which removal restores symmetry. The guarantee of a one-deletion fix lets you commit after a single retest.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo-pointer palindrome with localized repair. Converge from the ends; the first asymmetry pins the answer to two candidates, and a single inner re-check (skip one side) chooses between them. The 'find the break, branch locally' shape generalizes to Valid Palindrome II and one-edit problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Palindrome II
Same two-pointer + one-skip idea, but return true/false instead of the index.
Valid Palindrome
Plain converging two pointers after filtering non-alphanumerics.
Longest Palindromic Subsequence
Coming soon
Allow many deletions → interval DP, not a single re-check.
Longest Palindromic Substring
Coming soon
Expand around centers — palindrome detection scaled to all substrings.

Same pattern

←

Making Anagrams

Continue · Next problem

Separate the Numbers

easyStrings0Frequently asked

Palindrome Index

Arrays & Hashing · 65 of 83 · 7 min

If s is already a palindrome, return -1. Otherwise return the 0-based index of the character to remove. If multiple indices work, any valid one is acceptable.

In plain English

Examples

Example 1

Input: s = "aaab"
Output: 3
Note: l=0 'a' vs r=3 'b' mismatch. Is s[1..3]="aab" a palindrome? No. So remove right index 3 → "aaa" is a palindrome.

Example 2

Input: s = "baa"
Output: 0
Note: l=0 'b' vs r=2 'a' mismatch. Is s[1..2]="aa" a palindrome? Yes. So remove left index 0 → "aa" is a palindrome.

Example 3

Input: s = "aaa"
Output: -1
Note: Already a palindrome; pointers cross with no mismatch → −1.

Constraints

1 ≤ |s| ≤ 10⁵
s consists of lowercase English letters
A valid answer always exists (remove at most one character)
Return any valid index, or −1 if already a palindrome

Clarifying questions4First question: What if it's already a palindrome?Explore questions

Q1.What if it's already a palindrome?
Return −1 — no removal is needed. The two-pointer loop completes without a mismatch.
Q2.Is a solution guaranteed?
Yes. The problem promises that removing at most one character yields a palindrome, so after the first mismatch one of the two sides is guaranteed to work.
Q3.If two indices both work, which do I return?
Any valid index. For 'aba' style ties, returning either symmetric position is accepted.
Q4.Do I need to build the resulting palindrome?
No — only the index. The internal palindrome re-check uses index bounds, not new strings, to stay O(1) space.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for converging two pointers on a palindrome and handle the 'which side to remove' decision with a single targeted re-check rather than brute-forcing every deletion.

Where candidates slip

Returning the first mismatch index without verifying which side actually fixes the palindrome, or forgetting the −1 case when the string is already a palindrome.

How to stand out

Explain that at the first mismatch only two candidates exist (left or right), and one O(n) sub-check decides between them — so the whole thing stays O(n), not O(n²).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Try Removing Each Index (Brute Force)	`O(n²)`	`O(n)`	State it to anchor correctness, then note it's O(n²) and that two pointers find the suspect directly.	Read
2	Two Pointers with One-Side Re-check (Optimal)Optimal	`O(n)`	`O(1)`	The intended answer — converge from the ends, and at the first mismatch run a single inner palindrome test to pick the side.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Try Removing Each Index (Brute Force)

TimeO(n²)SpaceO(n)

State it to anchor correctness, then note it's O(n²) and that two pointers find the suspect directly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The answer is some index i to delete. What's the most direct way to test a candidate?

2Hint 2Explore hint

For each i, form s with index i removed and check whether it's a palindrome.

3Hint 3Explore hint

Return the first i that works, or −1 if s is already a palindrome. Note this is n palindrome checks → O(n²).

A · Core idea

Literally enumerate the answer: for each index i, delete it and test the result for palindromicity. Return the first index that produces a palindrome; if none is needed, return −1.

Why it's correct. The answer is by definition 'some index whose removal yields a palindrome'. Trying them all cannot miss it, and the first hit is a valid answer (the problem accepts any).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "baa"

Array state

remove 0

"aa" → palindrome

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result0

C · Code with teaching comments

solution.javaJava

Try Removing Each Index (Brute Force) — reference

3 teaching notes

1
public int palindromeIndex(String s) {
2
    // Already a palindrome → no deletion needed.
3
    if (isPalindrome(s, 0, s.length() - 1)) return -1;
4
    for (int i = 0; i < s.length(); i++) {
5
        // Build s with index i removed — O(n) per candidate.
6
        String candidate = s.substring(0, i) + s.substring(i + 1);
7
        if (isPalindrome(candidate, 0, candidate.length() - 1)) return i;
8
    }
9
    return -1;
10
}
11
 
12
private boolean isPalindrome(String s, int l, int r) {
13
    while (l < r) {
14
        if (s.charAt(l) != s.charAt(r)) return false;
15
        l++;
16
        r--;
17
    }
18
    return true;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5s = "a" — Single char is a palindrome → −1.Explore edge cases

Edge cases handled

s = "a"Single char is a palindrome → −1.
s = "ab"Remove index 0 → "b" palindrome → returns 0.

Pitfalls

O(n²) is too slow for n = 10⁵.
Rebuilding strings repeatedly wastes O(n) memory per try.
Forgetting the already-palindrome → −1 short-circuit.

03.2

Approach 2 of 2 · Optimal

Two Pointers with One-Side Re-check (Optimal)

TimeO(n)SpaceO(1)

The intended answer — converge from the ends, and at the first mismatch run a single inner palindrome test to pick the side.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Checking a palindrome is a converging two-pointer walk. Where does that walk first break?

2Hint 2Explore hint

At the first l/r mismatch, the removable character is either s[l] or s[r] — nothing else.

3Hint 3Explore hint

Test whether skipping left (s[l+1..r]) is a palindrome: if yes return l, else return r. If the walk never breaks, return −1.

A · Core idea

Set l = 0, r = n − 1. While s[l] == s[r], advance l++, r--. If the loop finishes, s is already a palindrome → return −1.

Why O(1) space. The inner check uses indices l+1 and r, walking inward with two more pointers — no substring is materialized.

Why this is O(n) not O(n²). Unlike brute force, there is at most a single inner check, and it runs once at the unique first mismatch — not once per index.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "aaab"

Array state

l=0,r=3

'a' vs 'b' → mismatch

l ↓

[0]

[1]

[2]

r ↓

[3]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Two Pointers with One-Side Re-check (Optimal) — optimal

5 teaching notes

1
public int palindromeIndex(String s) {
2
    int l = 0, r = s.length() - 1;
3
    // Converge from both ends — the palindrome check itself.
4
    while (l < r) {
5
        // First asymmetry: the answer is index l or r.
6
        if (s.charAt(l) != s.charAt(r)) {
7
            // Skipping left makes it a palindrome → remove left.
8
            if (isPalindrome(s, l + 1, r)) return l;
9
            // Otherwise the guaranteed fix is removing right.
10
            return r;
11
        }
12
        l++;
13
        r--;
14
    }
15
    // Loop finished with no mismatch → already a palindrome.
16
    return -1;
17
}
18
 
19
private boolean isPalindrome(String s, int l, int r) {
20
    while (l < r) {
21
        if (s.charAt(l) != s.charAt(r)) return false;
22
        l++;
23
        r--;
24
    }
25
    return true;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s = "racecar" — Already a palindrome → loop completes → −1.Explore edge cases

Edge cases handled

s = "racecar"Already a palindrome → loop completes → −1.
s = "abca"Mismatch at l=1 'b' vs r=2 'c'. Skip left → "c" palindrome → return 1 (remove 'b').
s = "aaab"Skip-left "aab" not a palindrome → return r = 3.

Pitfalls

Returning the mismatch index without the inner re-check to pick the correct side.
Materializing substrings for the inner check instead of using index bounds (O(n) space).
Missing the −1 path when the string is already a palindrome.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Guessing the side at the mismatch

At the first mismatch either s[l] or s[r] could be the culprit. Returning l (or r) without a re-check is wrong half the time — e.g. 'aaab' needs r, 'baa' needs l.

Explore the code comparison

Don't write this

if s[l] != s[r]:
    return l   # blind guess

Write this instead

if s[l] != s[r]:
    return l if is_pal(l + 1, r) else r

Forgetting the already-palindrome case

If the loop never hits a mismatch the string is a palindrome and the answer is −1; falling through to return 0 (or l) is incorrect.

Explore the code comparison

Don't write this

while (l < r) { if (s.charAt(l) != s.charAt(r)) { ... } l++; r--; }
return 0;

Write this instead

while (l < r) { if (s.charAt(l) != s.charAt(r)) { ... } l++; r--; }
return -1;

Copying substrings for the inner check

Building s[l+1..r] as a new string costs O(n) memory and time on every call; pass index bounds instead to keep O(1) space.

Explore the code comparison

Don't write this

sub = s[l + 1:r + 1]
if sub == sub[::-1]: return l

Write this instead

if is_pal(l + 1, r): return l

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-pointer scan + one-side palindrome retest

Code pattern to memorize

l, r = 0, n-1
while l < r:
    if s[l] != s[r]:
        if isPalindrome(s, l+1, r): return l
        else: return r
    l++, r--
return -1

Rules to remember

1At the first mismatch the removable index is left or right — decide by retesting the narrowed range.
2Test s[l+1..r] (skip left): if it's a palindrome, removing left works → return l.
3Otherwise removing right must work (the problem guarantees a solution) → return r.
4No mismatch through the whole scan → already a palindrome → return −1.
5The guarantee 'removing at most one char makes it a palindrome' means you never need to test both deeply.

Use this pattern when

Symmetric (palindrome) property checked from both ends
You may remove exactly one element and must locate which
A single localized mismatch decides the answer
O(1) extra space is desired — pointers, no copies

Choose another pattern when

More than one deletion allowed → becomes a DP (longest palindromic subsequence)
Need the resulting string, not the index → build it after deciding
Insertions allowed instead of deletions → min-insertions DP
Case/space normalization required → preprocess first (Valid Palindrome II family)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Palindrome II
Same two-pointer + one-skip idea, but return true/false instead of the index.
Valid Palindrome
Plain converging two pointers after filtering non-alphanumerics.
Longest Palindromic Subsequence
Coming soon
Allow many deletions → interval DP, not a single re-check.
Longest Palindromic Substring
Coming soon
Expand around centers — palindrome detection scaled to all substrings.

Same pattern

←

Making Anagrams

Continue · Next problem

Separate the Numbers