Daily Dose of DSA - Day 17

Question Link: https://practice.geeksforgeeks.org/problems/palindromic-patitioning4845/1

Recursion + Brute Force + Slight Memoization (Top-down DP)(TLE)(O(n^3) TC & O(n^2) SC)

// User function Template for C++
typedef long long ll;
class Solution{
public:
ll dp[501][501];

bool isPalindrome(string str, int i, int j) {
    while (i < j) {
        if (str[i] != str[j])
            return false;
        i++;
        j--;
    }
    return true;
}

ll rec(string str, int i, int j) {
    // Base case: If the substring is already a palindrome, no partition needed
    if (i >= j || isPalindrome(str, i, j))
        return 0;

    // If the subproblem has already been solved, return the result
    if (dp[i][j] != -1)
        return dp[i][j];

    ll ans = INT_MAX;

    // Partition the string at every possible position and calculate the minimum cuts
    for (int k = i; k < j; k++) {
        ll left = rec(str, i, k);
        ll right = rec(str, k + 1, j);
        ans = min(ans, left + right + 1);
    }

    // Store the minimum value in the dp table for memoization
    return dp[i][j] = ans;
}

    int palindromicPartition(string str)
    {
        // code here
          int n = str.length();

    memset(dp, -1, sizeof(dp));

    return rec(str, 0, n - 1);
    }
};

1. The function palindromicPartition initializes the dp table and calls the recursive function rec, which takes O(1) time. The memset operation takes O(n^2) time since it fills the entire dp table.

2. The recursive function rec is called for each substring of the input string. There are a total of n^2 substrings in the worst case. This is because there are n choices for the starting index and n choices for the ending index. Therefore, the total number of recursive calls is O(n^2).

3. Inside the rec function, there is a loop that partitions the string at every possible position. This loop iterates from i to j-1, where i and j represent the starting and ending indices of the current substring. In the worst case, the length of the substring is n, so the loop runs n times.

4. Inside the loop, the function makes recursive calls to rec for the left and right partitions of the substring. These recursive calls are made n times in the worst case since the loop runs n times.

5. Overall, for each recursive call, there is a loop that runs n times, and inside the loop, there are recursive calls made n times. Hence, the worst-case time complexity can be approximated as O(n n n) = O(n^3).

Therefore, the worst-case time complexity of the given solution is O(n^3).

---

Recursion + Memoization (Top-down DP)(O(n^3) TC & O(n^2) SC)

typedef long long ll;

class Solution {
public:
    ll dp[501][501];

    // Function to check if a substring is a palindrome
    bool isPalindrome(string str, int i, int j) {
        while (i < j) {
            if (str[i] != str[j])
                return false;
            i++;
            j--;
        }
        return true;
    }

    // Recursive function to calculate the minimum cuts
    int rec(string str, int i, int j) {
        // Base case: If the substring is already a palindrome, no partition needed
        if (i >= j || isPalindrome(str, i, j))
            return 0;

        // If the subproblem has already been solved, return the result from the dp table
        if (dp[i][j] != -1)
            return dp[i][j];

        int ans = INT_MAX;

        for (int k = i; k < j; k++) {
            int left, right;

            // Calculate the minimum cuts for the left and right substrings
            if (dp[i][k] != -1)
                left = dp[i][k];
            else {
                left = rec(str, i, k);
                dp[i][k] = left; // Memoize the result in the dp table
            }

            if (dp[k + 1][j] != -1)
                right = dp[k + 1][j];
            else {
                right = rec(str, k + 1, j);
                dp[k + 1][j] = right; // Memoize the result in the dp table
            }

            // Find the minimum cuts among all possible partitions
            ans = min(ans, left + right + 1);
        }

        dp[i][j] = ans; // Store the minimum cuts in the dp table for memoization
        return ans;
    }

    int palindromicPartition(string str) {
        int n = str.length();

        // Initialize the dp table with -1 (indicating subproblems that haven't been solved yet)
        memset(dp, -1, sizeof(dp));

        // Call the recursive function to calculate the minimum cuts
        return rec(str, 0, n - 1);
    }
};

The time complexity of the provided code is O(n^3), where n is the length of the input string.

The recursive function rec is called for each substring of the input string. For each substring of length n, there are O(n^2) possible substrings. In the worst case, for each substring, the function checks if it is a palindrome, which takes O(n) time. Therefore, the time complexity of the recursive function is O(n^3).Hence, the overall time complexity of the code is O(n^3) in the worst case.

---

Iteration + Tabulation (Bottom-up DP)(O(n^3) TC & O(n) SC)

typedef long long ll;
class Solution{
public:
    ll dp[501];

    bool isPalindrome(string str, int i, int j) {
        while (i < j) {
            if (str[i] != str[j])
                return false;
            i++;
            j--;
        }
        return true;
    }

    int palindromicPartition(string str) {
        int n = str.length();

        memset(dp, 0, sizeof(dp));

        for (int i = n - 1; i >= 0; i--) {
            dp[i] = INT_MAX;

            for (int j = i; j < n; j++) {
                if (isPalindrome(str, i, j)) {
                    if (j == n - 1)
                        dp[i] = 0;  // No partition needed if the substring is already a palindrome
                    else
                        dp[i] = min(dp[i], dp[j + 1] + 1);  // Partition the string and calculate the minimum cuts
                }
            }
        }

        return dp[0];
    }
};

The worst-case time complexity of the provided code is O(n^3), where n is the length of the input string. This occurs when the input string is such that all possible substrings need to be checked for palindrome, resulting in a nested loop structure. In the worst case, for each starting index i, the inner loop runs n - i times, and within that, the isPalindrome function checks each substring of length j - i + 1, which can be up to n. Hence, the overall time complexity is O(n^3) in the worst case.

---

Iteration + Tabulation (Bottom-up DP) (O(n^3)TC & O(n^2)SC)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int palindromicPartition(string str) {
        int n = str.length();

        // Create a dp table to store the minimum cuts for substrings
        vector<vector<int>> dp(n, vector<int>(n, 0));

        // Create a boolean table to store the palindrome information for substrings
        vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));

        // Initialize the dp table and isPalindrome table for substrings of length 1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
            isPalindrome[i][i] = true;
        }

        // Build the dp table and isPalindrome table bottom-up for substrings of increasing length
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                // Check if the current substring is a palindrome
                if (str[i] == str[j] && (len == 2 || isPalindrome[i + 1][j - 1]))
                    isPalindrome[i][j] = true;

                // If the substring is a palindrome, no partition needed
                if (isPalindrome[i][j])
                    dp[i][j] = 0;
                else {
                    dp[i][j] = INT_MAX;

                    // Partition the substring at every possible position and calculate the minimum cuts
                    for (int k = i; k < j; k++)
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);
                }
            }
        }

        // The minimum number of cuts for the entire string is stored in dp[0][n-1]
        return dp[0][n - 1];
    }
};

The time complexity of the given solution is O(n^3), where n is the length of the input string.

The solution uses a bottom-up dynamic programming (DP) approach to solve the problem. It builds a DP table of size n x n, where each entry dp[i][j] represents the minimum cuts required to partition the substring str[i...j] into palindromic substrings.

The solution iterates over the substrings of increasing length (len) from 2 to n. For each substring, it checks if it is a palindrome using the isPalindrome table, which takes constant time. If the substring is a palindrome, no partition is needed, so dp[i][j] is set to 0. Otherwise, the substring is partitioned at every possible position (k) within the substring, and the minimum cuts are calculated as dp[i][k] + dp[k+1][j] + 1.

Since the solution iterates over substrings of length 2 to n and checks all possible positions for partitioning, the time complexity is O(n^3).

Therefore, the given solution has a time complexity of O(n^3) in the worst case.

---