Horje
GeeksforGeeks Problem Of The Day POTD Solutions | 24 October 23

View all POTD Solutions

Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Dynamic Programming but will also help you build up problem-solving skills.

We recommend you to try this problem on our GeeksforGeeks Practice portal first, and maintain your streak to earn Geeksbits and other exciting prizes, before moving towards the solution.

POTD 24 October: Palindromic Partitioning

Given a string str, a partitioning of the string is a palindrome partitioning if every sub-string of the partition is a palindrome. Determine the fewest cuts needed for palindrome partitioning of the given string.

Example:

Input: str = “ababbbabbababa”
Output: 3
Explanation: After 3 partitioning substrings are “a”, “babbbab”, “b”, “ababa”.

Input: str = “aaabba”
Output: 1
Explanation: The substrings after 1 partitioning are “aa” and “abba”.

Palindromic Partitioning using Dynamic Programming:

The problem can be solved by finding the suffix starting from j and ending at index i, (1 <= j <= i <= n – 1), which are palindromes. Hence, we can make a cut here that requires 1 + min cut from rest substring [0, j – 1]. For all such palindromic suffixes starting at j and ending at i, keep minimising in minCutDp[i]. Similarly, we need to compute results for all such i. (1 <= i <= n – 1) and finally, minCutDp[n – 1] will be the minimum number of cuts needed for palindrome partitioning of the given string.

Below is the implementation of the above approach:

C++

class Solution {
public:
    // Function to generate all possible palindromic
    // substring
    bool generatePalindrome(string& str,
                            vector<vector<bool> >& pal)
    {
        int n = str.size();
  
        // Initialize the palindrome matrix for single
        // characters
        for (int i = 0; i < n; i++) {
            pal[i][i] = true;
        }
  
        // Iterate over different lengths of substrings
        for (int len = 2; len <= n; len++) {
            // Iterate over the starting positions of
            // substrings of current length
            for (int i = 0; i <= n - len; i++) {
  
                // Calculate the ending position of the
                // substring
                int j = i + len - 1;
  
                // Check if the characters at the starting
                // and ending positions are equal and if the
                // substring between them is a palindrome or
                // a single character
                if (str[i] == str[j]
                    && (len == 2 || pal[i + 1][j - 1])) {
  
                    // Mark the substring from i to j as a
                    // palindrome
                    pal[i][j] = true;
                }
            }
        }
    }
  
    int palindromicPartition(string str)
    {
        if (str.empty())
            return 0;
        int n = str.size();
  
        // 2D vector to store whether substring [i, j] is a
        // palindrome
        vector<vector<bool> > pal(n,
                                  vector<bool>(n, false));
  
        generatePalindrome(str, pal);
  
        // vector to store minimum cuts required to make
        // substring [i, n-1] palindromic
        vector<int> minCutDp(n, INT_MAX);
  
        // There is no cut required for single character
        // as it is always palindrome
        minCutDp[0] = 0;
  
        // Iterate over the given string
        for (int i = 1; i < n; i++) {
  
            // Check if string 0 to i is palindrome.
            // Then minCut require will be 0.
            if (pal[0][i]) {
                minCutDp[i] = 0;
            }
            else {
                for (int j = i; j >= 1; j--) {
  
                    // If str[i] and str[j] are equal and
                    // the inner substring [i+1, j-1] is a
                    // palindrome or it has a length of 1
                    if (pal[j][i]) {
  
                        // Update the minimum cuts required
                        // if cutting at position 'j+1'
                        // results in a smaller value
                        if (minCutDp[j - 1] + 1
                            < minCutDp[i])
                            minCutDp[i]
                                = minCutDp[j - 1] + 1;
                    }
                }
            }
        }
  
        // Return the minimum cuts required for the entire
        // string 'str'
        return minCutDp[n - 1];
    }
};

Java

class Solution {
    static int palindromicPartition(String str)
    {
        int n = str.length();
        boolean[][] pal = new boolean[n][n];
  
        // Function to generate all possible palindromic
        // substrings
        for (int i = 0; i < n; i++) {
            pal[i][i]
                = true; // Single characters are palindromes
        }
  
        // Iterate over different lengths of substrings
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
  
                // Check if the characters at the starting
                // and ending positions are equal and if the
                // substring between them is a palindrome or
                // a single character.
                if (str.charAt(i) == str.charAt(j)
                    && (len == 2 || pal[i + 1][j - 1])) {
                    pal[i][j]
                        = true; // Mark the substring from i
                                // to j as a palindrome
                }
            }
        }
  
        int[] minCutDp = new int[n];
        for (int i = 0; i < n; i++) {
            minCutDp[i]
                = Integer.MAX_VALUE; // Initialize the
                                     // minimum cut array
                                     // with maximum values
        }
        minCutDp[0]
            = 0; // No cuts needed for a single character
  
        // Iterate over the given string
        for (int i = 1; i < n; i++) {
            if (pal[0][i]) {
                minCutDp[i]
                    = 0; // If string 0 to i is a
                         // palindrome, no cut is required.
            }
            else {
                for (int j = i; j >= 1; j--) {
                    if (pal[j][i]) {
                        // If str[i] and str[j] are equal
                        // and the inner substring [i+1,
                        // j-1] is a palindrome or a single
                        // character, update the minimum
                        // cuts required if cutting at
                        // position 'j+1' results in a
                        // smaller value.
                        if (minCutDp[j - 1] + 1
                            < minCutDp[i]) {
                            minCutDp[i]
                                = minCutDp[j - 1] + 1;
                        }
                    }
                }
            }
        }
  
        // Return the minimum cuts required for the entire
        // string 'str'
        return minCutDp[n - 1];
    }
}

Python3

class Solution:
    def generatePalindrome(self, string):
        n = len(string)
  
        # Initialize the palindrome matrix for single characters
        pal = [[False] * n for _ in range(n)]
        for i in range(n):
            pal[i][i] = True
  
        # Iterate over different lengths of substrings
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if string[i] == string[j] and (length == 2 or pal[i + 1][j - 1]):
                    pal[i][j] = True
  
        return pal
  
    def palindromicPartition(self, string):
        if not string:
            return 0
        n = len(string)
  
        # 2D list to store whether substring [i, j] is a palindrome
        pal = [[False] * n for _ in range(n)]
        pal = self.generatePalindrome(string)
  
        # List to store minimum cuts required to make substring [i, n-1] palindromic
        minCutDp = [float('inf')] * n
  
        # There is no cut required for a single character as it is always palindrome
        minCutDp[0] = 0
  
        # Iterate over the given string
        for i in range(1, n):
            # Check if string 0 to i is a palindrome. Then minCut required will be 0.
            if pal[0][i]:
                minCutDp[i] = 0
            else:
                for j in range(i, 0, -1):
                    if pal[j][i]:
                        if minCutDp[j - 1] + 1 < minCutDp[i]:
                            minCutDp[i] = minCutDp[j - 1] + 1
  
        # Return the minimum cuts required for the entire string 'str'
        return minCutDp[n - 1]

Time Complexity: O(n2)
Auxiliary Space: O(n2)


 


Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
GeeksforGeeks Problem Of The Day POTD Solutions | 23 October 23 GeeksforGeeks Problem Of The Day POTD Solutions | 23 October 23
GeeksforGeeks Problem Of The Day POTD Solutions | 22 October 23 GeeksforGeeks Problem Of The Day POTD Solutions | 22 October 23
GeeksforGeeks Problem Of The Day POTD Solutions | 21 October 23 GeeksforGeeks Problem Of The Day POTD Solutions | 21 October 23
GeeksforGeeks Problem Of The Day POTD Solutions | 20 October 23 GeeksforGeeks Problem Of The Day POTD Solutions | 20 October 23
GeeksforGeeks Problem Of The Day POTD Solutions | 19 October 23 GeeksforGeeks Problem Of The Day POTD Solutions | 19 October 23

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje