Longest Almost-Palindromic Substring - Solution & Explanation

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.