Palindrome (回文)

def is_palindrome_two_pointers(s):
    """
    Basic palindrome check using two pointers
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric characters (for valid palindrome problems)
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
            
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
            
        left += 1
        right -= 1
    
    return True

// Java version
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            
            if (Character.toLowerCase(s.charAt(left)) != 
                Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
}

def longest_palindromic_substring(s):
    """
    Find longest palindromic substring using center expansion
    Time: O(n²), Space: O(1)
    """
    if not s:
        return ""
    
    start, max_len = 0, 1
    
    def expand_around_center(left, right):
        # Expand while characters match
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1  # Length of palindrome
    
    for i in range(len(s)):
        # Check for odd-length palindromes (center at i)
        len1 = expand_around_center(i, i)
        # Check for even-length palindromes (center between i and i+1)
        len2 = expand_around_center(i, i + 1)
        
        current_max = max(len1, len2)
        if current_max > max_len:
            max_len = current_max
            start = i - (current_max - 1) // 2
    
    return s[start:start + max_len]

// Java version
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        int start = 0, end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);     // odd length
            int len2 = expandAroundCenter(s, i, i + 1); // even length
            int len = Math.max(len1, len2);
            
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        return s.substring(start, end + 1);
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

def count_palindromic_substrings(s):
    """
    Count all palindromic substrings using DP
    Time: O(n²), Space: O(n²)
    """
    n = len(s)
    # dp[i][j] = True if s[i:j+1] is palindrome
    dp = [[False] * n for _ in range(n)]
    count = 0
    
    # Single characters are palindromes
    for i in range(n):
        dp[i][i] = True
        count += 1
    
    # Check for palindromes of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1
    
    # Check for palindromes of length 3+
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            # Check if s[i:j+1] is palindrome
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1
    
    return count

# Space-optimized version using center expansion
def count_palindromic_substrings_optimized(s):
    """
    Time: O(n²), Space: O(1)
    """
    count = 0
    
    def expand_and_count(left, right):
        nonlocal count
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    
    for i in range(len(s)):
        # Odd length palindromes
        expand_and_count(i, i)
        # Even length palindromes
        expand_and_count(i, i + 1)
    
    return count

def palindrome_partitioning(s):
    """
    Find all palindrome partitions using backtracking
    Time: O(n * 2^n), Space: O(n)
    """
    result = []
    current_partition = []
    
    def is_palindrome(start, end):
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True
    
    def backtrack(start):
        # Base case: reached end of string
        if start >= len(s):
            result.append(current_partition[:])
            return
        
        # Try all possible endings for current substring
        for end in range(start, len(s)):
            # If current substring is palindrome
            if is_palindrome(start, end):
                current_partition.append(s[start:end + 1])
                backtrack(end + 1)
                current_partition.pop()
    
    backtrack(0)
    return result

# Optimized with memoization
def palindrome_partitioning_memo(s):
    """
    With palindrome check memoization
    """
    n = len(s)
    # Precompute palindrome checks
    is_palin = [[False] * n for _ in range(n)]
    
    # Fill palindrome table
    for i in range(n):
        is_palin[i][i] = True
    
    for i in range(n - 1):
        is_palin[i][i + 1] = (s[i] == s[i + 1])
    
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_palin[i][j] = (s[i] == s[j] and is_palin[i + 1][j - 1])
    
    result = []
    current_partition = []
    
    def backtrack(start):
        if start >= n:
            result.append(current_partition[:])
            return
        
        for end in range(start, n):
            if is_palin[start][end]:
                current_partition.append(s[start:end + 1])
                backtrack(end + 1)
                current_partition.pop()
    
    backtrack(0)
    return result

def longest_palindromic_subsequence(s):
    """
    Find length of longest palindromic subsequence using DP
    Time: O(n²), Space: O(n²)
    """
    n = len(s)
    # dp[i][j] = length of LPS in s[i:j+1]
    dp = [[0] * n for _ in range(n)]
    
    # Single characters have LPS length 1
    for i in range(n):
        dp[i][i] = 1
    
    # Fill for substrings of length 2+
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    return dp[0][n - 1]

# Space-optimized version
def longest_palindromic_subsequence_optimized(s):
    """
    Time: O(n²), Space: O(n)
    """
    n = len(s)
    dp = [1] * n
    
    for i in range(n - 2, -1, -1):
        prev = 0
        for j in range(i + 1, n):
            temp = dp[j]
            if s[i] == s[j]:
                dp[j] = prev + 2
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp
    
    return dp[n - 1]

def is_palindrome_number(x):
    """
    Check if integer is palindrome without converting to string
    Time: O(log x), Space: O(1)
    """
    # Negative numbers are not palindromes
    if x < 0:
        return False
    
    # Single digit numbers are palindromes
    if x < 10:
        return True
    
    # Numbers ending in 0 (except 0) are not palindromes
    if x % 10 == 0:
        return False
    
    reversed_half = 0
    
    # Reverse only half of the number
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10
    
    # For even length: x == reversed_half
    # For odd length: x == reversed_half // 10
    return x == reversed_half or x == reversed_half // 10

// Java version
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        
        int reversedHalf = 0;
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }
        
        return x == reversedHalf || x == reversedHalf / 10;
    }
}

Problem Analysis Flowchart:

1. Is this a simple validation problem (check if input is palindrome)?
   ├── YES → Use Template 1: Two Pointers
   │   ├── String/Array input → Two pointers from ends
   │   ├── Linked List input → Two pointers + reverse half
   │   └── Integer input → Template 6: Number Palindrome
   └── NO → Continue to 2

2. Do you need to find/count palindromic substrings?
   ├── YES → 
   │   ├── Find longest substring → Template 2: Center Expansion
   │   ├── Count all substrings → Template 2: Center Expansion (optimized)
   │   └── Complex substring queries → Template 3: Dynamic Programming
   └── NO → Continue to 3

3. Do you need to partition/construct palindromes?
   ├── YES →
   │   ├── Find all partitions → Template 4: Backtracking
   │   ├── Minimum cuts needed → Template 3: DP + preprocessing
   │   └── Construct specific palindrome → Advanced techniques
   └── NO → Continue to 4

4. Do you need to modify string to make it palindrome?
   ├── YES →
   │   ├── Minimum insertions/deletions → Template 5: DP Subsequence
   │   ├── With k operations allowed → Template 3: DP with constraints
   │   └── Optimal transformation → Advanced DP techniques
   └── NO → Continue to 5

5. Is this a number-based palindrome problem?
   ├── YES → Template 6: Number Palindrome
   │   ├── Check palindrome number → Mathematical reversal
   │   ├── Generate palindromes → Mathematical construction
   │   └── Complex number constraints → Advanced math
   └── NO → Continue to 6

6. Advanced/Complex palindrome problem?
   ├── YES → Hybrid approach needed
   │   ├── Multiple patterns combined → Use multiple templates
   │   ├── Additional constraints → Modify existing templates
   │   └── Novel problem type → Design custom solution
   └── NO → Re-analyze problem requirements

# Basic two pointers
def is_palindrome_basic(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

# With character filtering
def is_palindrome_alphanumeric(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

# Allow one mismatch
def is_palindrome_one_delete(s):
    def helper(left, right, deleted):
        while left < right:
            if s[left] != s[right]:
                if deleted:  # Already used one delete
                    return False
                # Try deleting left or right character
                return (helper(left + 1, right, True) or 
                       helper(left, right - 1, True))
            left += 1
            right -= 1
        return True
    return helper(0, len(s) - 1, False)

# Standard center expansion
def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

# With counting
def count_palindromes_at_center(s, left, right):
    count = 0
    while left >= 0 and right < len(s) and s[left] == s[right]:
        count += 1
        left -= 1
        right += 1
    return count

# For all centers
def find_all_palindromes(s):
    palindromes = []
    for i in range(len(s)):
        # Odd length
        left, right = i, i
        while left >= 0 and right < len(s) and s[left] == s[right]:
            palindromes.append(s[left:right+1])
            left -= 1
            right += 1
        # Even length
        left, right = i, i + 1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            palindromes.append(s[left:right+1])
            left -= 1
            right += 1
    return palindromes

# Space optimization: 2D DP to 1D
def longest_palindromic_subsequence_1D(s):
    n = len(s)
    dp = [1] * n  # dp[j] represents length for current i to j
    
    for i in range(n - 2, -1, -1):
        prev = 0  # dp[i+1][j-1]
        for j in range(i + 1, n):
            temp = dp[j]  # Save current dp[j] for next iteration's prev
            if s[i] == s[j]:
                dp[j] = prev + 2
            else:
                dp[j] = max(dp[j], dp[j-1])
            prev = temp
    
    return dp[n-1]

# Preprocessing palindrome table
def precompute_palindromes(s):
    n = len(s)
    is_palin = [[False] * n for _ in range(n)]
    
    # Single characters
    for i in range(n):
        is_palin[i][i] = True
    
    # Two characters
    for i in range(n - 1):
        is_palin[i][i+1] = (s[i] == s[i+1])
    
    # Three+ characters
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_palin[i][j] = (s[i] == s[j] and is_palin[i+1][j-1])
    
    return is_palin

// LC 5 - Longest Palindromic Substring
// IDEA: Expand around center — O(N^2) with O(1) space
// time = O(N^2), space = O(1)
public String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        // odd length
        int len1 = expand(s, i, i);
        // even length
        int len2 = expand(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}
private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

// LC 125 - Valid Palindrome
// IDEA: Two pointers — skip non-alphanumeric, compare chars
// time = O(N), space = O(1)
public boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
        if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;
        l++; r--;
    }
    return true;
}

// LC 647 - Palindromic Substrings
// IDEA: Expand around center — count all palindromes
// time = O(N^2), space = O(1)
public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += expand(s, i, i);     // odd length
        count += expand(s, i, i + 1); // even length
    }
    return count;
}
private int expand(String s, int l, int r) {
    int cnt = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        cnt++; l--; r++;
    }
    return cnt;
}

// LC 9 - Palindrome Number
// IDEA: Reverse second half; compare with first half (avoids string conversion)
// time = O(log N), space = O(1)
public boolean isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int rev = 0;
    while (x > rev) { rev = rev * 10 + x % 10; x /= 10; }
    return x == rev || x == rev / 10;  // even/odd length
}

// LC 680 - Valid Palindrome II
// IDEA: Two pointers — on mismatch, try skipping left or right character
// time = O(N), space = O(1)
public boolean validPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r))
            return isPalin(s, l+1, r) || isPalin(s, l, r-1);
        l++; r--;
    }
    return true;
}
private boolean isPalin(String s, int l, int r) {
    while (l < r) { if (s.charAt(l++) != s.charAt(r--)) return false; }
    return true;
}

// LC 234 - Palindrome Linked List
// IDEA: Find mid (slow/fast), reverse second half, compare with first half
// time = O(N), space = O(1)
public boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode rev = reverse(slow);
    ListNode p = head, q = rev;
    while (q != null) { if (p.val != q.val) return false; p = p.next; q = q.next; }
    return true;
}
private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; }
    return prev;
}

// LC 516 - Longest Palindromic Subsequence
// IDEA: Interval DP — dp[i][j] = LPS length of s[i..j]
// time = O(N^2), space = O(N^2)
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++)
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j)
                ? dp[i+1][j-1] + 2
                : Math.max(dp[i+1][j], dp[i][j-1]);
        }
    return dp[0][n-1];
}

// LC 1216 - Valid Palindrome III
// IDEA: min deletions to make palindrome = N - LPS(s); answer = (N - LPS) <= k
// time = O(N^2), space = O(N^2)
public boolean isValidPalindrome(String s, int k) {
    int n = s.length();
    int[][] dp = new int[n][n];                 // dp[i][j] = LPS length of s[i..j]
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++)
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j)
                ? dp[i+1][j-1] + 2
                : Math.max(dp[i+1][j], dp[i][j-1]);
        }
    return n - dp[0][n-1] <= k;
}

# python
# LC 1216 - Valid Palindrome III
# IDEA: min deletions to make palindrome = N - LPS(s); answer = (N - LPS) <= k
# time = O(N^2), space = O(N^2)
def isValidPalindrome(s, k):
    n = len(s)
    dp = [[0] * n for _ in range(n)]            # dp[i][j] = LPS length of s[i..j]
    for i in range(n):
        dp[i][i] = 1
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = (dp[i+1][j-1] + 2) if s[i] == s[j] else max(dp[i+1][j], dp[i][j-1])
    return n - dp[0][n-1] <= k

// LC 1312 - Minimum Insertion Steps to Make String Palindrome
// IDEA: minInsertions = s.length() - LPS(s)
// time = O(N^2), space = O(N^2)
public int minInsertions(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; len++)
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = s.charAt(i) == s.charAt(j)
                ? dp[i+1][j-1]
                : Math.min(dp[i+1][j], dp[i][j-1]) + 1;
        }
    return dp[0][n-1];
}

// LC 131 - Palindrome Partitioning
// IDEA: Backtracking — at each position try all palindromic prefixes; recurse on suffix
// time = O(N * 2^N), space = O(N)
public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), res);
    return res;
}
private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
    if (start == s.length()) { res.add(new ArrayList<>(path)); return; }
    for (int end = start + 1; end <= s.length(); end++) {
        String sub = s.substring(start, end);
        if (isPalin(sub)) {
            path.add(sub);
            backtrack(s, end, path, res);
            path.remove(path.size() - 1);
        }
    }
}
private boolean isPalin(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

// LC 132 - Palindrome Partitioning II
// IDEA: DP — dp[i] = min cuts for s[0..i]; precompute isPalin table
// time = O(N^2), space = O(N^2)
public int minCut(String s) {
    int n = s.length();
    boolean[][] isPalin = new boolean[n][n];
    for (int i = n-1; i >= 0; i--)
        for (int j = i; j < n; j++)
            isPalin[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || isPalin[i+1][j-1]);
    int[] dp = new int[n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    for (int i = 0; i < n; i++) {
        if (isPalin[0][i]) { dp[i] = 0; continue; }
        for (int j = 1; j <= i; j++)
            if (isPalin[j][i]) dp[i] = Math.min(dp[i], dp[j-1] + 1);
    }
    return dp[n-1];
}

// LC 1542 - Find Longest Awesome Substring
// IDEA: Prefix XOR bitmask; awesome substring iff XOR has at most 1 set bit
// time = O(10 * N), space = O(1024)
public int longestAwesome(String s) {
    int[] seen = new int[1024];
    Arrays.fill(seen, s.length());
    seen[0] = -1;
    int prefix = 0, ans = 0;
    for (int i = 0; i < s.length(); i++) {
        prefix ^= 1 << (s.charAt(i) - '0');
        if (seen[prefix] <= s.length()) ans = Math.max(ans, i - seen[prefix]);
        else seen[prefix] = i;
        for (int d = 0; d <= 9; d++) {  // try one odd-count digit
            int mask = prefix ^ (1 << d);
            if (seen[mask] <= s.length()) ans = Math.max(ans, i - seen[mask]);
        }
    }
    return ans;
}

// java
// LC 5 - Longest Palindromic Substring (Manacher)
// IDEA: transform s -> ^#a#b#a#$ so all palindromes are odd length; reuse mirror radii inside [center, right]
// time = O(N), space = O(N)
public String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) return "";
    StringBuilder sb = new StringBuilder("^");        // ^ and $ are sentinels: stop expansion, no bounds check
    for (char c : s.toCharArray()) sb.append('#').append(c);
    sb.append("#$");
    char[] t = sb.toString().toCharArray();
    int n = t.length;
    int[] p = new int[n];                              // p[i] = palindrome radius at i (== length in original s)
    int center = 0, right = 0;
    for (int i = 1; i < n - 1; i++) {
        if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);   // mirror trick
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++;              // expand beyond what was reused
        if (i + p[i] > right) { center = i; right = i + p[i]; }         // new rightmost palindrome
    }
    int best = 0, bestCenter = 0;
    for (int i = 1; i < n - 1; i++)
        if (p[i] > best) { best = p[i]; bestCenter = i; }
    int start = (bestCenter - best) / 2;               // map back to index in s
    return s.substring(start, start + best);
}

# python
# LC 5 - Longest Palindromic Substring (Manacher)
# IDEA: transform s -> ^#a#b#a#$ so all palindromes are odd length; reuse mirror radii inside [center, right]
# time = O(N), space = O(N)
def longestPalindrome(s):
    if not s:
        return ""
    t = "^#" + "#".join(s) + "#$"                  # sentinels ^ $ never match -> no bounds check
    n = len(t)
    p = [0] * n                                    # p[i] = radius at i == palindrome length in original s
    center = right = 0
    for i in range(1, n - 1):
        if i < right:
            p[i] = min(right - i, p[2 * center - i])   # mirror trick
        while t[i + p[i] + 1] == t[i - p[i] - 1]:      # expand beyond reused radius
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    best = max(range(1, n - 1), key=lambda i: p[i])
    start = (best - p[best]) // 2                  # map back to index in s
    return s[start:start + p[best]]

// java
// LC 214 - Shortest Palindrome
// IDEA: longest palindromic prefix = KMP failure value of (s + "#" + reverse(s)); prepend the reversed remainder
// time = O(N), space = O(N)
public String shortestPalindrome(String s) {
    if (s.length() < 2) return s;
    String rev = new StringBuilder(s).reverse().toString();
    String t = s + "#" + rev;                     // '#' must not appear in s -> blocks overlap
    int[] fail = new int[t.length()];             // fail[i] = longest proper prefix that is also suffix of t[0..i]
    for (int i = 1; i < t.length(); i++) {
        int j = fail[i - 1];
        while (j > 0 && t.charAt(i) != t.charAt(j)) j = fail[j - 1];
        if (t.charAt(i) == t.charAt(j)) j++;
        fail[i] = j;
    }
    int longestPalPrefix = fail[t.length() - 1];
    return new StringBuilder(s.substring(longestPalPrefix)).reverse() + s;
}

# python
# LC 214 - Shortest Palindrome
# IDEA: longest palindromic prefix = KMP failure value of (s + "#" + reverse(s)); prepend the reversed remainder
# time = O(N), space = O(N)
def shortestPalindrome(s):
    if len(s) < 2:
        return s
    t = s + "#" + s[::-1]                      # '#' must not appear in s -> blocks overlap
    fail = [0] * len(t)                        # fail[i] = longest proper prefix == suffix of t[0..i]
    for i in range(1, len(t)):
        j = fail[i - 1]
        while j > 0 and t[i] != t[j]:
            j = fail[j - 1]
        if t[i] == t[j]:
            j += 1
        fail[i] = j
    return s[fail[-1]:][::-1] + s              # prepend reverse of the non-palindromic tail

// java
// LC 336 - Palindrome Pairs
// IDEA: split each word at every cut; palindromic half + reversed other half looked up in a HashMap
// time = O(N * L^2), space = O(N * L)
public List<List<Integer>> palindromePairs(String[] words) {
    Map<String, Integer> idx = new HashMap<>();
    for (int i = 0; i < words.length; i++) idx.put(words[i], i);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < words.length; i++) {
        String w = words[i];
        for (int j = 0; j <= w.length(); j++) {          // note: <= so the empty suffix is covered
            String prefix = w.substring(0, j), suffix = w.substring(j);
            if (isPalin(prefix)) {                       // rev(suffix) + prefix + suffix
                Integer k = idx.get(new StringBuilder(suffix).reverse().toString());
                if (k != null && k != i) res.add(Arrays.asList(k, i));
            }
            if (j < w.length() && isPalin(suffix)) {     // j < len avoids double-counting equal-length pairs
                Integer k = idx.get(new StringBuilder(prefix).reverse().toString());
                if (k != null && k != i) res.add(Arrays.asList(i, k));
            }
        }
    }
    return res;
}
// isPalin(...) — reuse the helper from section 2-9

# python
# LC 336 - Palindrome Pairs
# IDEA: split each word at every cut; palindromic half + reversed other half looked up in a dict
# time = O(N * L^2), space = O(N * L)
def palindromePairs(words):
    idx = {w: i for i, w in enumerate(words)}
    res = []
    for i, w in enumerate(words):
        for j in range(len(w) + 1):                  # note: +1 so the empty suffix is covered
            prefix, suffix = w[:j], w[j:]
            if prefix == prefix[::-1]:               # rev(suffix) + prefix + suffix
                k = idx.get(suffix[::-1])
                if k is not None and k != i:
                    res.append([k, i])
            if j < len(w) and suffix == suffix[::-1]:  # j < len avoids double-counting equal-length pairs
                k = idx.get(prefix[::-1])
                if k is not None and k != i:
                    res.append([i, k])
    return res