Problem statement

https://binarysearch.com/problems/Longest-Rotated-Palindromic-Substring/

Solution

Create s + s string and then find the longest substring, but such that it is not longer than n.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        s2 = s + s

        n, ans = len(s), 1
        def helper(i, j):
            while i >= 0 and j < 2*n and j - i + 1 <= n and s2[i] == s2[j]:
                i, j = i - 1, j + 1
            return j - i - 1
        
        for k in range(2*n):
            ans = max(helper(k, k), helper(k, k + 1), ans)
        return ans

Remark

In fact we can apply Manacher algorithm here and then apply rescriction that length is <= n. Time complexity will be O(n).