Skip to content

2911. Minimum Changes to Make K Semi-palindromes

  • Time: $O(n^2k) = O(n^3)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
 public:
  int minimumChanges(string s, int k) {
    const int n = s.length();
    // factors[i] := factors of i
    const vector<vector<int>> factors = getFactors(n);
    // cost[i][j] := changes to make s[i..j] a semi-palindrome
    const vector<vector<int>> cost = getCost(s, n, factors);
    // dp[i][j] := the minimum changes to split s[i:] into j valid parts
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, n));

    dp[n][0] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int j = 1; j <= k; ++j)
        for (int l = i + 1; l < n; ++l)
          dp[i][j] = min(dp[i][j], dp[l + 1][j - 1] + cost[i][l]);

    return dp[0][k];
  }

 private:
  vector<vector<int>> getFactors(int n) {
    vector<vector<int>> factors(n + 1);
    for (int i = 1; i <= n; ++i)
      factors[i].push_back(1);
    for (int d = 2; d < n; ++d)
      for (int i = d * 2; i <= n; i += d)
        factors[i].push_back(d);
    return factors;
  }

  vector<vector<int>> getCost(const string& s, int n,
                              const vector<vector<int>>& factors) {
    vector<vector<int>> cost(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        const int length = j - i + 1;
        int minCost = length;
        for (const int d : factors[length])
          minCost = min(minCost, getCost(s, i, j, d));
        cost[i][j] = minCost;
      }
    return cost;
  }

  // Returns the cost to make s[i..j] a semi-palindrome of `d`.
  int getCost(const 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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
  public int minimumChanges(String s, int k) {
    final int n = s.length();
    // factors[i] := factors of i
    List<Integer>[] factors = getFactors(n);
    // cost[i][j] := changes to make s[i..j] a semi-palindrome
    int[][] cost = getCost(s, n, factors);
    // dp[i][j] := the minimum changes to split s[i:] into j valid parts
    int[][] dp = new int[n + 1][k + 1];

    Arrays.stream(dp).forEach(A -> Arrays.fill(A, n));
    dp[n][0] = 0;

    for (int i = n - 1; i >= 0; --i)
      for (int j = 1; j <= k; ++j)
        for (int 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];
  }

  private List<Integer>[] getFactors(int n) {
    List<Integer>[] factors = new List[n + 1];
    for (int i = 1; i <= n; ++i)
      factors[i] = new ArrayList<>(List.of(1));
    for (int d = 2; d < n; ++d)
      for (int i = d * 2; i <= n; i += d)
        factors[i].add(d);
    return factors;
  }

  private int[][] getCost(final String s, int n, List<Integer>[] factors) {
    int[][] cost = new int[n][n];
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j) {
        final int length = j - i + 1;
        int minCost = length;
        for (final int d : factors[length])
          minCost = Math.min(minCost, getCost(s, i, j, d));
        cost[i][j] = minCost;
      }
    return cost;
  }

  // Returns the cost to make s[i..j] a semi-palindrome of `d`.
  private int getCost(final 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.charAt(l) != s.charAt(r))
          ++cost;
        l += d;
        r -= d;
      }
    }
    return cost;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
  def minimumChanges(self, s: str, k: int) -> int:
    n = len(s)
    # factors[i] := factors of i
    factors = self._getFactors(n)
    # cost[i][j] := changes to make s[i..j] a semi-palindrome
    cost = self._getCost(s, n, factors)
    # dp[i][j] := the minimum changes to split s[i:] into j valid parts
    dp = [[n] * (k + 1) for _ in range(n + 1)]

    dp[n][0] = 0

    for i in range(n - 1, -1, -1):
      for j in range(1, k + 1):
        for l in range(i + 1, n):
          dp[i][j] = min(dp[i][j], dp[l + 1][j - 1] + cost[i][l])

    return dp[0][k]

  def _getFactors(self, n: int) -> list[list[int]]:
    factors = [[1] for _ in range(n + 1)]
    for d in range(2, n):
      for i in range(d * 2, n + 1, d):
        factors[i].append(d)
    return factors

  def _getCost(self, s: str, n: int, factors: list[list[int]]) -> list[list[int]]:
    cost = [[0] * n for _ in range(n)]
    for i in range(n):
      for j in range(i + 1, n):
        length = j - i + 1
        minCost = length
        for d in factors[length]:
          minCost = min(minCost, self._getCostD(s, i, j, d))
        cost[i][j] = minCost
    return cost

  def _getCostD(self, s: str, i: int, j: int, d: int) -> int:
    """Returns the cost to make s[i..j] a semi-palindrome of `d`."""
    cost = 0
    for offset in range(d):
      l = i + offset
      r = j - d + 1 + offset
      while l < r:
        if s[l] != s[r]:
          cost += 1
        l += d
        r -= d
    return cost