Constraints

• 0 <= len(s) <= 200000
• s may contain letters, digits, spaces, punctuation, and Unicode characters
• Use Unicode-aware alphanumeric checks and case folding

Examples

Solution

def solution(s):
    normalized = []
    for ch in s:
        if ch.isalnum():
            for fch in ch.casefold():
                if fch.isalnum():
                    normalized.append(fch)
    return normalized == normalized[::-1]

Time complexity: O(n). Space complexity: O(n).

Hints

1. Build the normalized sequence first: keep only alphanumeric characters and apply case folding.
2. After normalization, palindrome checking is just a compare against the reversed sequence.

Constraints

• 0 <= len(s) <= 100000
• locale_code is one of 'default', 'tr', or 'az'
• Use NFKD normalization and strip combining marks with Unicode-aware logic

Examples

Solution

import unicodedata

def solution(s, locale_code):
    if locale_code in ('tr', 'az'):
        mapping = {'I': 'ı', 'İ': 'i'}
        s = ''.join(mapping.get(ch, ch) for ch in s)

    folded = s.casefold()
    decomposed = unicodedata.normalize('NFKD', folded)

    normalized = []
    for ch in decomposed:
        if unicodedata.combining(ch):
            continue
        if ch.isalnum():
            normalized.append(ch)

    return normalized == normalized[::-1]

Time complexity: O(n). Space complexity: O(n).

Hints

1. The Turkish/Azeri dotted-I rule must be handled before generic case folding, otherwise 'I' and 'İ' lose their distinction.
2. Use unicodedata.normalize('NFKD', ...) and skip characters where unicodedata.combining(ch) is nonzero.

Constraints

• The total number of characters across all chunks can be very large
• Each chunk must be processed in order and should not require storing the full normalized string
• Use O(1) extra space beyond a constant number of integers

Examples

Solution

def solution(chunks):
    base = 911382323
    mod1 = 1000000007
    mod2 = 1000000009

    forward1 = 0
    forward2 = 0
    reverse1 = 0
    reverse2 = 0
    power1 = 1
    power2 = 1

    for chunk in chunks:
        for ch in chunk:
            if not ch.isalnum():
                continue
            for fch in ch.casefold():
                if not fch.isalnum():
                    continue
                x = ord(fch) + 1
                forward1 = (forward1 * base + x) % mod1
                forward2 = (forward2 * base + x) % mod2
                reverse1 = (reverse1 + x * power1) % mod1
                reverse2 = (reverse2 + x * power2) % mod2
                power1 = (power1 * base) % mod1
                power2 = (power2 * base) % mod2

    return forward1 == reverse1 and forward2 == reverse2

Time complexity: O(n). Space complexity: O(1).

Hints

1. Maintain both a forward polynomial hash and a reverse-position polynomial hash as characters arrive.
2. Use two different moduli to make collisions extremely unlikely.

Constraints

• 0 <= len(s) <= 2000 after normalization
• 0 <= k <= 2000
• An O(n^2) dynamic programming solution is expected

Examples

Solution

def solution(s, k):
    normalized = []
    for ch in s:
        if ch.isalnum():
            for fch in ch.casefold():
                if fch.isalnum():
                    normalized.append(fch)

    n = len(normalized)
    if n <= 1:
        return True
    if k >= n:
        return True

    dp = [0] * n

    for i in range(n - 2, -1, -1):
        prev = 0
        for j in range(i + 1, n):
            temp = dp[j]
            if normalized[i] == normalized[j]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(dp[j], dp[j - 1])
            prev = temp

    return dp[n - 1] <= k

Time complexity: O(n^2). Space complexity: O(n).

Hints

1. Think in terms of the minimum number of deletions needed to make a substring a palindrome.
2. Equivalent viewpoint: minimum deletions = length - longest palindromic subsequence.

Constraints

• 0 <= len(s) <= 200000
• Indices in the answer refer to positions in the original input string
• Use Unicode-aware alphanumeric checks and case folding

Examples

Solution

def solution(s):
    normalized = []
    original_indices = []

    for idx, ch in enumerate(s):
        if ch.isalnum():
            for fch in ch.casefold():
                if fch.isalnum():
                    normalized.append(fch)
                    original_indices.append(idx)

    left = 0
    right = len(normalized) - 1

    while left < right:
        if normalized[left] != normalized[right]:
            return (original_indices[left], original_indices[right])
        left += 1
        right -= 1

    return (-1, -1)

Time complexity: O(n). Space complexity: O(n).

Hints

1. Store both the normalized characters and the original index each normalized character came from.
2. Then run a normal two-pointer palindrome check on the normalized list and return the mapped original indices at the first mismatch.