2911. Minimum Changes to Make K Semi-palindromes

Description

Given a string s and an integer k, partition s into k such that the letter changes needed to make each substring a semi-palindrome are minimized.

Return the minimum number of letter changes required.

A semi-palindrome is a special type of string that can be divided into based on a repeating pattern. To check if a string is a semi-palindrome:​

1. Choose a positive divisor d of the string's length. d can range from 1 up to, but not including, the string's length. For a string of length 1, it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed.
2. For a given divisor d, divide the string into groups where each group contains characters from the string that follow a repeating pattern of length d. Specifically, the first group consists of characters at positions 1, 1 + d, 1 + 2d, and so on; the second group includes characters at positions 2, 2 + d, 2 + 2d, etc.
3. The string is considered a semi-palindrome if each of these groups forms a palindrome.

Consider the string "abcabc":

• The length of "abcabc" is 6. Valid divisors are 1, 2, and 3.
• For d = 1: The entire string "abcabc" forms one group. Not a palindrome.
• For d = 2:
  • Group 1 (positions 1, 3, 5): "acb"
  • Group 2 (positions 2, 4, 6): "bac"
  • Neither group forms a palindrome.
• For d = 3:
  • Group 1 (positions 1, 4): "aa"
  • Group 2 (positions 2, 5): "bb"
  • Group 3 (positions 3, 6): "cc"
  • All groups form palindromes. Therefore, "abcabc" is a semi-palindrome.

 

Example 1:

Input: s = "abcac", k = 2

Output: 1

Explanation: Divide s into "ab" and "cac". "cac" is already semi-palindrome. Change "ab" to "aa", it becomes semi-palindrome with d = 1.

Example 2:

Input: s = "abcdef", k = 2

Output: 2

Explanation: Divide s into substrings "abc" and "def". Each needs one change to become semi-palindrome.

Example 3:

Input: s = "aabbaa", k = 3

Output: 0

Explanation: Divide s into substrings "aa", "bb" and "aa". All are already semi-palindromes.

 

Constraints:

• 2 <= s.length <= 200
• 1 <= k <= s.length / 2
• s contains only lowercase English letters.

 

Solutions

Solution: Sieve of Eratosthenes + Dynamic Programming

• Time complexity: O(n²k)
• Space complexity: O(nk)

 

JavaScript

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
const minimumChanges = function (s, k) {
  const n = s.length;
  const factors = getFactors(n);
  const cost = getCost(s, n, factors);
  const dp = Array.from({ length: n + 1 }, () => new Array(k + 1).fill(n));

  dp[n][0] = 0;

  for (let i = n - 1; i >= 0; i--) {
    for (let j = 1; j <= k; j++) {
      for (let l = i + 1; l < n; l++) {
        dp[i][j] = Math.min(dp[i][j], dp[l + 1][j - 1] + cost[i][l]);
      }
    }
  }

  return dp[0][k];
};

function getFactors(n) {
  const factors = Array.from({ length: n + 1 }, () => []);

  for (let index = 1; index <= n; index++) {
    factors[index].push(1);
  }

  for (let d = 2; d < n; d++) {
    for (let index = d * 2; index <= n; index += d) {
      factors[index].push(d);
    }
  }

  return factors;
}

function calcSubCost(s, i, j, d) {
  let cost = 0;

  for (let offset = 0; offset < d; ++offset) {
    let l = i + offset;
    let r = j - d + 1 + offset;

    while (l < r) {
      if (s[l] !== s[r]) {
        ++cost;
      }

      l += d;
      r -= d;
    }
  }

  return cost;
}

function getCost(s, n, factors) {
  const cost = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let i = 0; i < n; ++i) {
    for (let j = i + 1; j < n; ++j) {
      const length = j - i + 1;
      let minCost = length;

      for (const d of factors[length]) {
        minCost = Math.min(minCost, calcSubCost(s, i, j, d));
      }

      cost[i][j] = minCost;
    }
  }

  return cost;
}