LeetCode 2911 | Minimum Changes to Make K Semi-palindromes | Java | Hard | DP & Math | CodeByTushu
Description: π Welcome Back to CodeByTushu!
In todayβs video, we solve LeetCode 2911 β Minimum Changes to Make K Semi-palindromes using Dynamic Programming, String Partitioning, and Divisor Checking in Java.
In this problem, we are given a string s and an integer k, and we need to partition s into k non-overlapping substrings such that the total number of character modifications required to make every substring a semi-palindrome is minimized. A semi-palindrome requires that for some proper divisor d of the substring length, characters grouped by their index modulo d form palindromes. Since a semi-palindrome must have length of at least 2 and a valid proper divisor d (where 1 is less than or equal to d and d is strictly less than the substring length), we must evaluate all valid divisors d and find the minimum letter changes needed for every possible contiguous substring.
To solve this efficiently, we employ a two-phase dynamic programming approach. First, we precompute the minimum changes cost[i][j] needed to make the substring s[i..j] a semi-palindrome by iterating over every proper divisor d and running a two-pointer palindrome match across the d residue classes. Second, we define dp[c][i] as the minimum changes to partition prefix s[0..i] into c semi-palindromes, transitioning by testing every valid previous split point p. This guarantees an optimal partition in polynomial time with strict boundary validation, handling all edge cases seamlessly.
π₯ Problem Highlights
β Two-stage dynamic programming architecture with divisor precomputation
β Exact evaluation of all proper divisors for each candidate substring length
β Two-pointer palindrome mismatch counting across interleaved residue classes
β Minimum changes DP transition partitioning the string into exactly k parts
β Strict length constraints ensuring each substring has length of at least 2
β Polynomial time complexity with minimal auxiliary memory overhead
β±οΈ TIMESTAMPS
00:00 Intro
01:01 Problem Understanding
02:38 Observation
04:32 Approach
06:03 Code Explanation
08:46 Code Run
10:23 Time Complexity
11:46 Space Complexity
12:41 Outro
π Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes
β Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/Solution.java
π Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/solution.py
β‘ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/solution.cpp
π JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/solution.js
π LeetCode Source Code
π https://codebytushu.com/leetcode/problem/minimum-changes-to-make-k-semi-palindromes
π All LeetCode Solutions
π https://codebytushu.com/Leetcode/
π± Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
β€οΈ Donate
π https://codebytushu.com/Leetcode/donate.php
π₯ Perfect For
LeetCode Hard Problems
Java DSA Preparation
Dynamic Programming Partitioning
Divisor and Number Theory Patterns
String Algorithms
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
π Follow CodeByTushu
βΆοΈ YouTube: https://www.youtube.com/@codebytushu
πΈ Instagram: https://instagram.com/codebytushu/
πΌ LinkedIn: https://www.linkedin.com/company/codebytushu/
π Website: https://codebytushu.com
π GitHub: https://github.com/CodeByTushu
β€οΈ Donβt Forget To
π Like | π¬ Comment | π Subscribe
π¬ Question of the Day
Why does a semi-palindrome substring require a length of at least 2?
1οΈβ£ A string of length 1 cannot be palindromic
2οΈβ£ Divisor d must be a proper divisor strictly less than length, which requires length at least 2
3οΈβ£ k must always divide string length n evenly
4οΈβ£ Dynamic programming states cannot store odd lengths
#LeetCode2911 #LeetCode #MinimumChangesToMakeKSemiPalindromes #Java #JavaDSA #DynamicProgramming #StringAlgorithms #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
π Comment the answer below! π₯Β Close description
In todayβs video, we solve LeetCode 2911 β Minimum Changes to Make K Semi-palindromes using Dynamic Programming, String Partitioning, and Divisor Checking in Java.
In this problem, we are given a string s and an integer k, and we need to partition s into k non-overlapping substrings such that the total number of character modifications required to make every substring a semi-palindrome is minimized. A semi-palindrome requires that for some proper divisor d of the substring length, characters grouped by their index modulo d form palindromes. Since a semi-palindrome must have length of at least 2 and a valid proper divisor d (where 1 is less than or equal to d and d is strictly less than the substring length), we must evaluate all valid divisors d and find the minimum letter changes needed for every possible contiguous substring.
To solve this efficiently, we employ a two-phase dynamic programming approach. First, we precompute the minimum changes cost[i][j] needed to make the substring s[i..j] a semi-palindrome by iterating over every proper divisor d and running a two-pointer palindrome match across the d residue classes. Second, we define dp[c][i] as the minimum changes to partition prefix s[0..i] into c semi-palindromes, transitioning by testing every valid previous split point p. This guarantees an optimal partition in polynomial time with strict boundary validation, handling all edge cases seamlessly.
π₯ Problem Highlights
β Two-stage dynamic programming architecture with divisor precomputation
β Exact evaluation of all proper divisors for each candidate substring length
β Two-pointer palindrome mismatch counting across interleaved residue classes
β Minimum changes DP transition partitioning the string into exactly k parts
β Strict length constraints ensuring each substring has length of at least 2
β Polynomial time complexity with minimal auxiliary memory overhead
β±οΈ TIMESTAMPS
00:00 Intro
01:01 Problem Understanding
02:38 Observation
04:32 Approach
06:03 Code Explanation
08:46 Code Run
10:23 Time Complexity
11:46 Space Complexity
12:41 Outro
π Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes
β Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/Solution.java
π Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/solution.py
β‘ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/solution.cpp
π JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/17-November/2911-Minimum-Changes-to-Make-K-Semi-palindromes/solution.js
π LeetCode Source Code
π https://codebytushu.com/leetcode/problem/minimum-changes-to-make-k-semi-palindromes
π All LeetCode Solutions
π https://codebytushu.com/Leetcode/
π± Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
β€οΈ Donate
π https://codebytushu.com/Leetcode/donate.php
π₯ Perfect For
LeetCode Hard Problems
Java DSA Preparation
Dynamic Programming Partitioning
Divisor and Number Theory Patterns
String Algorithms
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
π Follow CodeByTushu
βΆοΈ YouTube: https://www.youtube.com/@codebytushu
πΈ Instagram: https://instagram.com/codebytushu/
πΌ LinkedIn: https://www.linkedin.com/company/codebytushu/
π Website: https://codebytushu.com
π GitHub: https://github.com/CodeByTushu
β€οΈ Donβt Forget To
π Like | π¬ Comment | π Subscribe
π¬ Question of the Day
Why does a semi-palindrome substring require a length of at least 2?
1οΈβ£ A string of length 1 cannot be palindromic
2οΈβ£ Divisor d must be a proper divisor strictly less than length, which requires length at least 2
3οΈβ£ k must always divide string length n evenly
4οΈβ£ Dynamic programming states cannot store odd lengths
#LeetCode2911 #LeetCode #MinimumChangesToMakeKSemiPalindromes #Java #JavaDSA #DynamicProgramming #StringAlgorithms #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
π Comment the answer below! π₯Β Close description




