Palindromo en java - formación de palindromos en subcadenas

Problema

el problema consiste en particionar la cadena en k partes y modificar el menor número posible de letras para que cada parte cumpla la propiedad de semipalíndromo.

Enfoque de la solución

Este es un problema de nivel Hard que combina dos técnicas importantes:

1. Precomputación del costo mínimo para convertir cada substring posible en semi-palindrome.
2. Dynamic Programming para encontrar la mejor forma de dividir el string en k partes.

Solución en Java

import java.util.*;

class Solution {
    public int minimumChanges(String s, int k) {
        int n = s.length();
        final int INF = 1_000_000_000;
        
        // g[i][j] = combios minimos para hacer un s[i..j-1] semi-palindrome
        int[][] g = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(g[i], INF);
        }
        
        // Precompute cost for every substring
        for (int i = 1; i <= n; i++) {           // start (1-based)
            for (int j = i; j <= n; j++) {       // end
                int len = j - i + 1;
                if (len == 1) continue; // longitud 1 no puede ser semi-palindrome
                
                for (int d = 1; d < len; d++) {
                    if (len % d != 0) continue;
                    
                    int changes = 0;
                    // For de este divisior d, checa cada grupo
                    for (int start = 0; start < d; start++) {
                        // Chaeca el grupo inicial 'start' con el paso d
                        int left = 0;
                        int right = (len / d) - 1;
                        while (left < right) {
                            char c1 = s.charAt(i - 1 + left * d + start);
                            char c2 = s.charAt(i - 1 + right * d + start);
                            if (c1 != c2) {
                                changes++;
                            }
                            left++;
                            right--;
                        }
                    }
                    g[i][j] = Math.min(g[i][j], changes);
                }
            }
        }
        
        // DP: dp[i][j] = consto minimo particionado primero i caracteres dentro de j partes
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                for (int prev = 0; prev < i; prev++) {
                    if (dp[prev][j - 1] != INF && g[prev + 1][i] != INF) {
                        dp[i][j] = Math.min(dp[i][j], dp[prev][j - 1] + g[prev + 1][i]);
                    }
                }
            }
        }
        
        return dp[n][k];
    }
}

Conceptos clave aprendidos

• Dynamic Programming de partición
• Precomputación de costos en substrings
• Divisores y patrones repetitivos en strings
• Optimización de soluciones complejas

Dificultad

Este tipo de problemas ayuda a fortalecer el razonamiento lógico y la capacidad de combinar múltiples técnicas algorítmicas.