LeetCode 647 — Palindromic Substrings

Sexto problema de DP 1-D. Variante directa de 5-longest-palindromic-substring: contar palíndromos en lugar de devolver el más largo.

Enunciado

Cuenta cuántos substrings palindrómicos hay (contando duplicados por posición).

---

Solución — Expand around center contando

class Solution:
    def countSubstrings(self, s):
        count = 0
 
        def expand(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)):
            expand(i, i)                         # impares
            expand(i, i+1)                       # pares
 
        return count

Análisis: O(n²).

---

Conexiones

• 5-longest-palindromic-substring — base.
• Próximo: 91-decode-ways.

Estado

• Leído
• Implementado desde cero
• Resuelto en LeetCode