2026-01-10 14:04:15 +0300 MSK

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        length = len(s)
        if length < 2:
            return s
        left = 0
        for right in reversed(range(length)):
            if s[left] == s[right]:
                left += 1
        if left == length:
            return s
        non_palindrome_suffix = s[left:]
        reverse_suffix = non_palindrome_suffix[::-1]
        return (
            reverse_suffix
            + self.shortestPalindrome(s[:left])
            + non_palindrome_suffix
        )