DDSA Solutions

2911. Minimum Changes to Make K Semi-palindromes

Time: O(n^3)
Space: O(n^2)

Problem Overview

A semi-palindrome is a string whose characters fall into residue classes under a proper divisor d of its length, and each class reads as a palindrome when stepped by d.

Intuition

A semi-palindrome is a string whose characters fall into residue classes under a proper divisor d of its length, and each class reads as a palindrome when stepped by d. For every substring, every proper divisor is tried and the mismatches along those stepped pairs are counted; the cheapest divisor becomes the substring cost. The original string must then be cut into exactly k such pieces. dp[i][j] stores the fewest changes needed to finish s[i:] using j pieces. The first piece ends at some index l, costs cost[i][l], and the remainder is solved with j minus 1 pieces. Each piece needs length at least 2, so the cut leaves enough characters for every later piece. With n at most 200, precomputing all substring costs and filling the partition table is practical.

Algorithm

  1. 1Precompute every proper divisor of each length up to n.
  2. 2For every substring s[i..j], try each proper divisor d and count stepped mismatches; store the minimum as cost[i][j].
  3. 3Set dp[n][0] = 0 and every other dp state to a large sentinel.
  4. 4For i from n minus 1 down to 0 and for each part count j, try every cut end l that leaves at least 2 characters for each remaining part.
  5. 5Update dp[i][j] with dp[l + 1][j - 1] plus cost[i][l].
  6. 6Return dp[0][k].

Example Walkthrough

Input: s = "abcac", k = 2

  1. 1.The substring abc can be made a semi-palindrome with one change, and ac already fits a semi-palindrome with no changes.
  2. 2.Splitting after the third character therefore costs 1 in total.
  3. 3.No cheaper split into two valid parts exists, so the answer is 1.

Output: 1

Common Pitfalls

  • •d must be a proper divisor of the substring length. Using d equal to the length is not allowed for a semi-palindrome.
  • •Every part needs length at least 2. Leaving a single character for a later part makes that state unreachable.
  • •Precompute costs once. Recomputing divisor mismatch scans inside the DP would multiply the work by another factor of n.
  • •Initialize unused dp cells to a sentinel at least n. Zero would look like a free partition.
2911.cs
C#
// Approach: Precompute cost[i][j] as the fewest changes that make s[i..j] a
// semi-palindrome: try every proper divisor d of the length and count
// mismatches along each residue class stepped by d. Then dp[i][j] is the
// fewest changes to split s[i:] into j semi-palindromes, taking the best
// first cut s[i..l]. Each part needs length at least 2, so later cuts leave
// room for the remaining parts.
// Time: O(n^3) Space: O(n^2)

public class Solution
{
    public int MinimumChanges(string s, int k)
    {
        int n = s.Length;
        List<int>[] factors = GetFactors(n);
        int[,] cost = GetCost(s, n, factors);
        int[,] dp = new int[n + 1, k + 1];

        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= k; ++j)
                dp[i, j] = n;
        dp[n, 0] = 0;

        for (int i = n - 1; i >= 0; --i)
        {
            for (int j = 1; j <= k; ++j)
            {
                // Leave at least 2 characters for each of the remaining j - 1 parts.
                int maxL = n - 1 - 2 * (j - 1);
                for (int l = i + 1; l <= maxL; ++l)
                    dp[i, j] = Math.Min(dp[i, j], dp[l + 1, j - 1] + cost[i, l]);
            }
        }

        return dp[0, k];
    }

    private static List<int>[] GetFactors(int n)
    {
        var factors = new List<int>[n + 1];
        for (int i = 1; i <= n; ++i)
            factors[i] = new List<int> { 1 };
        for (int d = 2; d < n; ++d)
            for (int i = d * 2; i <= n; i += d)
                factors[i].Add(d);
        return factors;
    }

    private static int[,] GetCost(string s, int n, List<int>[] factors)
    {
        int[,] cost = new int[n, n];
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                int length = j - i + 1;
                int minCost = length;
                foreach (int d in factors[length])
                    minCost = Math.Min(minCost, ChangeCost(s, i, j, d));
                cost[i, j] = minCost;
            }
        }
        return cost;
    }

    private static int ChangeCost(string s, int i, int j, int d)
    {
        int cost = 0;
        for (int offset = 0; offset < d; ++offset)
        {
            int l = i + offset;
            int r = j - d + 1 + offset;
            while (l < r)
            {
                if (s[l] != s[r])
                    ++cost;
                l += d;
                r -= d;
            }
        }
        return cost;
    }
}
Was this solution helpful?

Related Problems