LeetCode Problem 3844

Difficulty: 🟡 Medium
Topics: Two Pointers, String, Dynamic Programming

Solution

LeetCode 3844 - Longest Almost-Palindromic Substring

Problem Understanding

We are given a string s consisting of lowercase English letters. We must find the length of the longest substring that is almost-palindromic.

A substring is almost-palindromic if we can remove exactly one character from that substring and the remaining characters form a palindrome.

The key detail is that we are free to choose:

1. Any substring of s.
2. Any single character inside that substring to remove.

If, after removing that one character, the remaining string reads the same forward and backward, then the substring is considered valid.

For example, in "abca", removing 'c' produces "aba", which is a palindrome. Therefore the entire substring "abca" is almost-palindromic and contributes length 4.

The string length can be as large as 2500, which immediately rules out very expensive approaches. There are roughly O(n²) substrings, so any solution that performs a full palindrome check for every substring would become far too slow.

Several edge cases are worth noting:

• A substring that is already a palindrome may still be almost-palindromic if removing one character leaves another palindrome. For example, "abba" becomes "aba" after removing one of the middle 'b' characters.
• Very short substrings must be handled correctly. For example, "aa" becomes "a" after deleting one character.
• The removable character may appear anywhere in the substring, not necessarily at one of the ends.
• The longest valid answer is not necessarily the longest palindrome. A non-palindromic substring may become a palindrome after one deletion.

Approaches

Brute Force

The most direct solution is to enumerate every substring.

For each substring, we try removing every possible character position. After each removal, we check whether the resulting string is a palindrome.

If any deletion produces a palindrome, the substring is almost-palindromic.

This approach is correct because it explicitly tests every valid deletion for every possible substring. However, it is extremely slow.

There are O(n²) substrings. A substring may have length O(n). For each substring we may try O(n) deletions, and each palindrome check costs O(n) time.

This leads to O(n⁴) time complexity, which is completely impractical for n = 2500.

Optimal Dynamic Programming

The crucial observation is that an almost-palindromic substring differs from a palindrome by exactly one removable character.

Let:

• pal[i][j] = whether s[i...j] is a palindrome.
• almost[i][j] = whether s[i...j] can become a palindrome after deleting one character.

The palindrome table is standard and can be computed in O(n²) time.

For the almost-palindromic table, consider the two ends:

• If the substring is already a palindrome, it is automatically almost-palindromic.
• If the end characters match, the decision depends entirely on the inner substring.
• If the end characters do not match, the one allowed deletion must remove either the left end or the right end. After that deletion, the remaining substring must be a palindrome.

This gives a simple dynamic programming recurrence that can be evaluated in O(n²) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n⁴)	O(1)	Enumerate all substrings, all deletions, and recheck palindromes
Optimal DP	O(n²)	O(n²)	Precompute palindrome and almost-palindromic states

Algorithm Walkthrough

1. Let n be the length of the string.
2. Build a DP table pal.

pal[i][j] is true if substring s[i...j] is a palindrome.

The standard recurrence is:

• Single characters are palindromes.
• Two end characters must match.
• The inner substring must also be a palindrome.

3. Build another DP table almost.

almost[i][j] is true if s[i...j] can become a palindrome after removing exactly one character. 4. Initialize all length-1 substrings as true.

Removing the single character leaves the empty string, which is a palindrome. 5. Process substrings in increasing order of length.

This guarantees that whenever we need information about smaller substrings, it has already been computed. 6. For a substring s[i...j]:

• If pal[i][j] is true, mark almost[i][j] as true.
• Otherwise, if s[i] == s[j], then the removable character must lie somewhere inside. Therefore:

almost[i][j] = almost[i+1][j-1]

• Otherwise, the ends mismatch. The one deletion must remove one of them:

• Delete the left end, leaving s[i+1...j].

• Delete the right end, leaving s[i...j-1].

One of those remaining substrings must already be a palindrome:

almost[i][j] = pal[i+1][j] or pal[i][j-1] 7. Whenever almost[i][j] becomes true, update the answer with the substring length. 8. Return the maximum length found.

Why it works

The recurrence exhausts all possible ways a single deletion can create a palindrome.

When the outer characters match, any valid deletion must occur inside the substring, so the problem reduces to the inner interval.

When the outer characters differ, the only possible single deletion that can repair the mismatch is removing one of those two ends. After that removal, the remaining substring must already be a palindrome.

Since every possibility is covered and every state depends only on smaller intervals, the DP computes the correct answer for every substring.

Python Solution

class Solution:
    def almostPalindromic(self, s: str) -> int:
        n = len(s)

        pal = [[False] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            pal[i][i] = True

            for j in range(i + 1, n):
                if s[i] == s[j]:
                    if j - i == 1 or pal[i + 1][j - 1]:
                        pal[i][j] = True

        almost = [[False] * n for _ in range(n)]

        answer = 1

        for i in range(n):
            almost[i][i] = True

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                if pal[i][j]:
                    almost[i][j] = True
                elif s[i] == s[j]:
                    almost[i][j] = almost[i + 1][j - 1]
                else:
                    almost[i][j] = pal[i + 1][j] or pal[i][j - 1]

                if almost[i][j]:
                    answer = length

        return answer

The implementation begins by constructing the palindrome DP table. Processing indices from right to left ensures that pal[i + 1][j - 1] has already been computed when needed.

After that, the almost table is built. Each state corresponds exactly to the recurrence derived above.

Whenever a valid almost-palindromic substring is discovered, the current substring length is recorded. Since lengths are processed in increasing order, the final value stored in answer is the maximum valid length.

Go Solution

func almostPalindromic(s string) int {
	n := len(s)

	pal := make([][]bool, n)
	for i := range pal {
		pal[i] = make([]bool, n)
	}

	for i := n - 1; i >= 0; i-- {
		pal[i][i] = true

		for j := i + 1; j < n; j++ {
			if s[i] == s[j] {
				if j-i == 1 || pal[i+1][j-1] {
					pal[i][j] = true
				}
			}
		}
	}

	almost := make([][]bool, n)
	for i := range almost {
		almost[i] = make([]bool, n)
	}

	answer := 1

	for i := 0; i < n; i++ {
		almost[i][i] = true
	}

	for length := 2; length <= n; length++ {
		for i := 0; i+length-1 < n; i++ {
			j := i + length - 1

			if pal[i][j] {
				almost[i][j] = true
			} else if s[i] == s[j] {
				almost[i][j] = almost[i+1][j-1]
			} else {
				almost[i][j] = pal[i+1][j] || pal[i][j-1]
			}

			if almost[i][j] {
				answer = length
			}
		}
	}

	return answer
}

The Go implementation follows the same DP structure as the Python version. The primary difference is explicit allocation of two-dimensional boolean slices. No special handling for integer overflow is required because all values are bounded by the string length, which is at most 2500.

Worked Examples

Example 1

Input:

s = "abca"

Palindrome DP Highlights

Substring	Palindrome
a	True
b	True
c	True
a	True
abc	False
bca	False
abca	False

Almost-Palindromic DP

Substring	Result
ab	True
bc	True
ca	True
abc	True
bca	True
abca	True

For "abca":

• Ends match (a == a).
• Check inner substring "bc".
• "bc" is almost-palindromic because deleting either character leaves a palindrome.
• Therefore "abca" is almost-palindromic.

Answer = 4.

Example 2

Input:

s = "abba"

For substring "abba":

i	j	Characters
0	3	a = a

The ends match, so we examine "bb".

"bb" is a palindrome, therefore it is also almost-palindromic.

Thus "abba" is almost-palindromic.

One valid deletion removes the second 'b':

abba -> aba

Answer = 4.

Example 3

Input:

s = "zzabba"

Consider the full string:

zzabba

The first and last characters do not match:

z != a

Check the two possible deletions:

Deletion	Remaining Substring	Palindrome?
Remove left end	zabba	No
Remove right end	zzabb	No

Therefore length 6 is invalid.

Now examine:

zabba

Deleting the first character yields:

abba

which is a palindrome.

Therefore "zabba" is almost-palindromic.

Answer = 5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Both DP tables contain O(n²) states and each state is computed in O(1)
Space	O(n²)	Two n × n boolean DP tables

The algorithm processes every substring exactly once in each DP table. Since there are n(n+1)/2 = O(n²) substrings and every transition takes constant time, the overall running time is O(n²). The two DP tables dominate memory usage, giving O(n²) space complexity.

Test Cases

sol = Solution()

assert sol.almostPalindromic("abca") == 4      # provided example
assert sol.almostPalindromic("abba") == 4      # provided example
assert sol.almostPalindromic("zzabba") == 5    # provided example

assert sol.almostPalindromic("aa") == 2        # smallest palindrome
assert sol.almostPalindromic("ab") == 2        # delete either character

assert sol.almostPalindromic("abc") == 3       # remove middle or an end
assert sol.almostPalindromic("aaa") == 3       # all identical characters

assert sol.almostPalindromic("aab") == 3       # delete trailing b
assert sol.almostPalindromic("baa") == 3       # delete leading b

assert sol.almostPalindromic("abcd") == 3      # no length-4 solution

assert sol.almostPalindromic("racecar") == 7   # palindrome remains valid

assert sol.almostPalindromic("abecbea") == 7   # delete c -> abebea -> palindrome

Test Summary

Test	Why
"abca"	Provided example
"abba"	Palindrome that remains valid after deletion
"zzabba"	Longest answer is a proper substring
"aa"	Minimum nontrivial palindrome
"ab"	Minimum length with distinct characters
"abc"	Entire string valid via one deletion
"aaa"	Repeated characters
"aab"	Delete last character
"baa"	Delete first character
"abcd"	No long valid substring
"racecar"	Odd-length palindrome
"abecbea"	Internal deletion required

Edge Cases

Already Palindromic Substrings

A common mistake is to assume that an almost-palindromic substring must contain exactly one mismatch. The examples show this is not true. A palindrome such as "abba" is valid because removing one of the middle characters leaves "aba", which is still a palindrome.

The implementation handles this through the condition if pal[i][j], which immediately marks the substring as almost-palindromic.

Mismatch at the Ends

Consider "abca". The outer characters match, but the interior is not a palindrome. The removable character lies inside the substring rather than at an end.

The recurrence almost[i][j] = almost[i + 1][j - 1] correctly delegates the decision to the interior interval.

Long Strings with No Large Valid Answer

Strings such as "abcd" contain no almost-palindromic substring of length four. A naive implementation may incorrectly accept them after multiple implicit deletions.

The DP only allows a single deletion. When the ends mismatch, it requires either pal[i + 1][j] or pal[i][j - 1] to already be a palindrome. This strictly enforces the one-deletion requirement and prevents invalid substrings from being accepted.