Minimum Changes to Make K Semi-palindromes solution and explanation

#include <iostream>
#include <vector>
#include <climits>
#include <cstring>

using namespace std;

int min(int a, int b) {
    return a < b ? a : b;
}

int palindrome_changes(const string &s, int start, int end) {
    int changes = 0;
    while (start < end) {
        if (s[start] != s[end]) {
            changes++;
        }
        start++;
        end--;
    }
    return changes;
}

int minChangesToMakeKPalindromes(const string &s, int k) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(k + 1, INT_MAX));

    for (int i = 0; i < n; ++i) {
        dp[i][1] = palindrome_changes(s, 0, i);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 2; j <= k; ++j) {
            for (int m = j - 1; m <= i; ++m) {
                dp[i][j] = min(dp[i][j], dp[m - 1][j - 1] + palindrome_changes(s, m, i));
            }
        }
    }

    return dp[n - 1][k];
}

int main() {
    string s = "abcac";
    int k = 2;
    cout << minChangesToMakeKPalindromes(s, k) << endl;
    return 0;
}

#include <stdio.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int palindrome_changes(char *s, int start, int end) {
    int changes = 0;
    while (start < end) {
        if (s[start] != s[end]) {
            changes++;
        }
        start++;
        end--;
    }
    return changes;
}

int minChangesToMakeKPalindromes(char *s, int n, int k) {
    int dp[n][k+1];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; ++i) {
        dp[i][1] = palindrome_changes(s, 0, i);
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 2; j <= k; ++j) {
            dp[i][j] = INT_MAX;
            for (int m = j-1; m <= i; ++m) {
                dp[i][j] = min(dp[i][j], dp[m-1][j-1] + palindrome_changes(s, m, i));
            }
        }
    }

    return dp[n-1][k];
}

int main() {
    char s[] = "abcac";
    int k = 2;
    int n = strlen(s);
    printf("%d\n", minChangesToMakeKPalindromes(s, n, k));
    return 0;
}

def min_changes_to_k_palindromes(s: str, k: int) -> int:
    def palindrome_changes(st, en):
        return sum(1 for i in range((en - st) // 2) if s[st + i] != s[en - i - 1])

    n = len(s)
    dp = [[float('inf')] * (k + 1) for _ in range(n)]

    for i in range(n):
        dp[i][1] = palindrome_changes(0, i + 1)

    for j in range(2, k + 1):
        for i in range(n):
            for m in range(j - 1, i + 1):
                dp[i][j] = min(dp[i][j], dp[m - 1][j - 1] + palindrome_changes(m, i + 1))

    return dp[n - 1][k]

print(min_changes_to_k_palindromes('abcac', 2))  # Output: 1

class SemiPalindrome {
    public int minChanges(String s, int k) {
        int n = s.length();
        int[][] dp = new int[n][k + 1];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);

        for (int i = 0; i < n; ++i) {
            dp[i][1] = palindromeChanges(s, 0, i);
        }

        for (int j = 2; j <= k; ++j) {
            for (int i = 0; i < n; ++i) {
                for (int m = j - 1; m <= i; ++m) {
                    dp[i][j] = Math.min(dp[i][j], dp[m - 1][j - 1] + palindromeChanges(s, m, i));
                }
            }
        }

        return dp[n - 1][k];
    }

    private int palindromeChanges(String s, int start, int end) {
        int changes = 0;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                changes++;
            }
            start++;
            end--;
        }
        return changes;
    }

    public static void main(String[] args) {
        SemiPalindrome sp = new SemiPalindrome();
        System.out.println(sp.minChanges("abcac", 2));  // Output: 1
    }
}

function minimumChanges(s: string, k: number): number {
    const n = s.length;
    const g = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => Infinity));
    const f = Array.from({ length: n + 1 }, () => Array.from({ length: k + 1 }, () => Infinity));
    f[0][0] = 0;
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= n; ++j) {
            const m = j - i + 1;
            for (let d = 1; d < m; ++d) {
                if (m % d === 0) {
                    let cnt = 0;
                    for (let l = 0; l < m; ++l) {
                        const r = (((m / d) | 0) - 1 - ((l / d) | 0)) * d + (l % d);
                        if (l >= r) {
                            break;
                        }
                        if (s[i - 1 + l] !== s[i - 1 + r]) {
                            ++cnt;
                        }
                    }
                    g[i][j] = Math.min(g[i][j], cnt);
                }
            }
        }
    }
    for (let i = 1; i <= n; ++i) {
        for (let j = 1; j <= k; ++j) {
            for (let h = 0; h < i - 1; ++h) {
                f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h + 1][i]);
            }
        }
    }
    return f[n][k];
}

func minimumChanges(s string, k int) int {
	n := len(s)
	g := make([][]int, n+1)
	f := make([][]int, n+1)
	const inf int = 1 << 30
	for i := range g {
		g[i] = make([]int, n+1)
		f[i] = make([]int, k+1)
		for j := range g[i] {
			g[i][j] = inf
		}
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	f[0][0] = 0
	for i := 1; i <= n; i++ {
		for j := i; j <= n; j++ {
			m := j - i + 1
			for d := 1; d < m; d++ {
				if m%d == 0 {
					cnt := 0
					for l := 0; l < m; l++ {
						r := (m/d-1-l/d)*d + l%d
						if l >= r {
							break
						}
						if s[i-1+l] != s[i-1+r] {
							cnt++
						}
					}
					g[i][j] = min(g[i][j], cnt)
				}
			}
		}
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= k; j++ {
			for h := 0; h < i-1; h++ {
				f[i][j] = min(f[i][j], f[h][j-1]+g[h+1][i])
			}
		}
	}
	return f[n][k]
}