3844. Longest Almost-Palindromic Substring

Description

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.

Solutions

Solution 1: Enumerate the Center Position of the Palindrome

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)\).

Python3JavaC++GoTypeScript

class Solution:
    def almostPalindromic(self, s: str) -> int:
        def f(l: int, r: int) -> int:
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            l1, r1 = l - 1, r
            l2, r2 = l, r + 1
            while l1 >= 0 and r1 < n and s[l1] == s[r1]:
                l1 -= 1
                r1 += 1
            while l2 >= 0 and r2 < n and s[l2] == s[r2]:
                l2 -= 1
                r2 += 1
            return min(n, max(r1 - l1 - 1, r2 - l2 - 1))

        n = len(s)
        ans = 0
        for i in range(n):
            a = f(i, i)
            b = f(i, i + 1)
            ans = max(ans, a, b)
        return ans

class Solution {
    private int n;
    private char[] s;

    public int almostPalindromic(String s) {
        n = s.length();
        this.s = s.toCharArray();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, f(i, i));
            ans = Math.max(ans, f(i, i + 1));
        }
        return ans;
    }

    private int f(int l, int r) {
        while (l >= 0 && r < n && s[l] == s[r]) {
            l--;
            r++;
        }

        int l1 = l - 1, r1 = r;
        int l2 = l, r2 = r + 1;

        while (l1 >= 0 && r1 < n && s[l1] == s[r1]) {
            l1--;
            r1++;
        }
        while (l2 >= 0 && r2 < n && s[l2] == s[r2]) {
            l2--;
            r2++;
        }

        return Math.min(n, Math.max(r1 - l1 - 1, r2 - l2 - 1));
    }
}

class Solution {
public:
    int almostPalindromic(string s) {
        int n = s.size();

        auto f = [&](int l, int r) {
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
            }

            int l1 = l - 1, r1 = r;
            int l2 = l, r2 = r + 1;

            while (l1 >= 0 && r1 < n && s[l1] == s[r1]) {
                --l1;
                ++r1;
            }
            while (l2 >= 0 && r2 < n && s[l2] == s[r2]) {
                --l2;
                ++r2;
            }

            return min(n, max(r1 - l1 - 1, r2 - l2 - 1));
        };

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, f(i, i));
            ans = max(ans, f(i, i + 1));
        }

        return ans;
    }
};

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

    f := func(l, r int) int {
        for l >= 0 && r < n && s[l] == s[r] {
            l--
            r++
        }

        l1, r1 := l-1, r
        l2, r2 := l, r+1

        for l1 >= 0 && r1 < n && s[l1] == s[r1] {
            l1--
            r1++
        }
        for l2 >= 0 && r2 < n && s[l2] == s[r2] {
            l2--
            r2++
        }
        return min(n, max(r1-l1-1, r2-l2-1))
    }

    ans := 0
    for i := 0; i < n; i++ {
        ans = max(ans, f(i, i), f(i, i+1))
    }
    return ans
}

function almostPalindromic(s: string): number {
    const n = s.length;

    const f = (l: number, r: number): number => {
        while (l >= 0 && r < n && s[l] === s[r]) {
            l--;
            r++;
        }

        let l1 = l - 1,
            r1 = r;
        let l2 = l,
            r2 = r + 1;

        while (l1 >= 0 && r1 < n && s[l1] === s[r1]) {
            l1--;
            r1++;
        }
        while (l2 >= 0 && r2 < n && s[l2] === s[r2]) {
            l2--;
            r2++;
        }

        return Math.min(n, Math.max(r1 - l1 - 1, r2 - l2 - 1));
    };

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans = Math.max(ans, f(i, i));
        ans = Math.max(ans, f(i, i + 1));
    }

    return ans;
}

3844. Longest Almost-Palindromic Substring

Description

Solutions

Solution 1: Enumerate the Center Position of the Palindrome

Comments