Skip to main content
Talentd

Longest Almost-Palindromic Substring - Solution & Explanation

MediumTwo PointersStringDynamic Programming10 min read
Practice this problem

Problem Statement

You are given a string s consisting of lowercase English letters.

A substring is almost-palindromic if it becomes a palindrome after removing exactly one character from it.

Return an integer denoting the length of the longest almost-palindromic substring in s.

 

Example 1:

Input: s = "abca"

Output: 4

Explanation:

Choose the substring "abca".

  • Remove "abca".
  • The string becomes "aba", which is a palindrome.
  • Therefore, "abca" is almost-palindromic.

Example 2:

Input: s = "abba"

Output: 4

Explanation:

Choose the substring "abba".

  • Remove "abba".
  • The string becomes "aba", which is a palindrome.
  • Therefore, "abba" is almost-palindromic.

Example 3:

Input: s = "zzabba"

Output: 5

Explanation:

Choose the substring "zzabba".

  • Remove "zabba".
  • The string becomes "abba", which is a palindrome.
  • Therefore, "zabba" is almost-palindromic.

 

Constraints:

  • 2 <= s.length <= 2500
  • s consists of only lowercase English letters.

Approach Overview

Problem Overview: You are given a string and need the length (or substring) of the longest segment that is almost a palindrome. An almost-palindromic substring allows at most one mismatch while comparing characters from both ends. The goal is to scan the string efficiently and find the longest such region.

Approach 1: Brute Force Substring Check (O(n^3) time, O(1) space)

Generate every possible substring using two nested loops. For each substring, run a two-pointer check from both ends and allow at most one mismatch before rejecting it. The validation step itself can take O(n) time, which makes the full algorithm O(n^3). This approach is useful for understanding the constraint and verifying correctness on small inputs, but it becomes too slow for large strings.

Approach 2: Dynamic Programming on Substrings (O(n^2) time, O(n^2) space)

Create a DP table where dp[i][j] represents whether the substring from index i to j can form an almost palindrome. You compare s[i] and s[j], and rely on the state of the inner substring dp[i+1][j-1] while tracking whether a mismatch has already occurred. This approach reduces repeated checks and guarantees O(n^2) time. The tradeoff is memory usage because the table stores results for every substring. It’s a common pattern in dynamic programming problems involving palindromes.

Approach 3: Enumerate the Center Position of the Palindrome (O(n^2) time, O(1) space)

Instead of checking every substring, treat each index (and each gap between indices) as the center of a potential palindrome. Expand outward with left and right pointers. When characters match, keep expanding normally. When a mismatch appears, allow it once and continue expanding while tracking that the mismatch has already been used. This mirrors the classic palindrome expansion technique but adds a single-error tolerance. The method uses two pointers and works directly on the string without extra memory. Since each center expansion takes O(n) in the worst case and there are O(n) centers, the overall complexity is O(n^2).

Recommended for interviews: Enumerating the center is the expected solution. Interviewers like it because it shows you understand palindrome structure and can optimize from brute force to a targeted expansion strategy. Starting with the brute-force idea demonstrates problem understanding, but the center-expansion approach proves you can reduce redundant checks and reach the optimal O(n^2) time with O(1) space.

Solution

Let's denote the length of string s as n.

We define a function f(l, r), which represents calculating the length of the longest almost-palindromic substring that can be obtained by starting from l and r, expanding towards both sides of the string, and deleting one character.

In the function f(l, r), we first expand towards both sides until the conditions l geq 0, r \lt n, and s[l] = s[r] are no longer satisfied. At this point, we can choose to skip l or skip r. If we skip l, then we continue to expand from (l - 1, r) towards both sides; if we skip r, then we continue to expand from (l, r + 1) towards both sides. We calculate the length of the longest almost-palindromic substring for both cases and take the maximum value. Note that the length of the longest almost-palindromic substring cannot exceed n.

Finally, we enumerate the center position i of the palindrome, and calculate the length of the longest almost-palindromic substring obtained by starting from (i, i) and (i, i + 1), expanding towards both sides, and deleting one character, taking the maximum value among them.

The time complexity is O(n^2), where n is the length of string s. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring + ValidationO(n^3)O(1)Small inputs or when first reasoning about the problem
Dynamic Programming TableO(n^2)O(n^2)When you want structured subproblem reuse for palindrome checks
Expand Around Center (Two Pointers)O(n^2)O(1)Best general solution; minimal memory and interview friendly

Video Solution

Longest Almost-Palindromic Substring | LeetCode 3844 | Modified Expand Around Center • Sanyam IIT Guwahati • 2,403 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Longest Almost-Palindromic Substring easy or hard?
This problem is typically rated Medium because the brute-force idea is simple but optimizing it requires recognizing the palindrome center property. Implementing expansion while correctly handling a single mismatch adds a small but important layer of complexity.
Longest Almost-Palindromic Substring Python/Java solution
Most implementations enumerate every center and expand outward while tracking whether a mismatch has already occurred. The same logic works across Python, Java, C++, Go, and TypeScript. Each expansion updates the maximum valid substring length found so far.
How to solve Longest Almost-Palindromic Substring in O(n)?
A strict O(n) algorithm is generally not used for this variant because allowing a mismatch complicates linear-time palindrome structures like Manacher’s algorithm. Most practical solutions rely on center expansion with O(n^2) time and constant space, which performs well for typical constraints.
What is the best approach for Longest Almost-Palindromic Substring?
The expand-around-center technique is the best practical approach. Treat each index and gap as a center, expand with two pointers, and allow at most one mismatch during expansion. This runs in O(n^2) time and uses O(1) space, making it efficient and simple to implement.
Is Longest Almost-Palindromic Substring asked at Google/Amazon/Meta?
Palindrome and near-palindrome substring problems frequently appear in interviews at large tech companies. Variants involving one allowed mismatch or deletion test knowledge of two pointers, string processing, and optimization from brute force to O(n^2) solutions.
What data structure is used in Longest Almost-Palindromic Substring?
The core technique uses two pointers operating directly on the string. Some implementations also use dynamic programming tables to store substring validity, but the most common interview solution avoids extra data structures and works with pointer expansion.
What is the time complexity of Longest Almost-Palindromic Substring?
The optimal approach runs in O(n^2) time using center expansion. Each character can act as a palindrome center and expansion may scan up to the full string length. Space complexity is O(1) because the algorithm only uses a few pointer variables.

Ready to solve this problem?

Practice Longest Almost-Palindromic Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water