Starting from a string, we determine it’s a palindrome partitioning by diving it into substrings, each being a palindrome. In our problem we will find out how many times we must cut the string in order to obtain a palindrome partitioning. So, if the string is divided into 2 subsequences, then it needs 1 cut. If all the letters from the string are different, then we need length -1 cuts.
Input: String input = "aabbbbabbabbaba"; Output: 3 Explanation: The Subsequences are: a, abbbba, bbabb, aba, so we need 3 cuts. |
Solution:
1. static int minimumPalindromePartitioning(String input) { 2. int inputLength = input.length(); 3. 4. int[] cuts = new int[inputLength]; 5. boolean[][] palindromes = new boolean[inputLength][inputLength]; 6. 7. for (int i = 0; i < inputLength; i++) { 8. palindromes[i][i] = true; 9. } 10. 11. for (int substringLength = 2; substringLength <= inputLength; substringLength++) { 12. for (int i = 0; i < inputLength - substringLength + 1; i++) { 13. int endingIndex = i + substringLength - 1; 14. boolean isPalindrome = input.charAt(i) == input.charAt(endingIndex); 15. palindromes[i][endingIndex] = (substringLength == 2) ? isPalindrome : (isPalindrome && palindromes[i + 1][endingIndex - 1]); 16. } 17. } 18. 19. for (int i = 0; i < inputLength; i++) { 20. if (palindromes[0][i]) { 21. cuts[i] = 0; 22. } else { 23. cuts[i] = Integer.MAX_VALUE; 24. for (int j = 0; j < i; j++) { 25. if (palindromes[j + 1][i] && 1 + cuts[j] < cuts[i]) { 26. cuts[i] = 1 + cuts[j]; 27. } 28. } 29. } 30. } 31. 32. return cuts[inputLength - 1]; 33. } 34.