Palindrome Partitioning Leetcode Solution

Hello and welcome back to another day of mindlessly solving Leetcode problems while you get rejected from every possible job at every company to ever exist.

Let's dive in!

Understanding The Problem

Here's the problem statement for today.

Given a string s, partition s such that every substring is a palindrome. Return all possible palindrome partitioning of s.

A palindrome is a string that is the same whether you read it from the beginning or from the end.

Let's see an example to make this problem clearer.

Example 1:

s = "aabaab"

Output: [["a","a","b","a","a","b"],["a","a","b","aa","b"],["a","a","baab"],["a","aba","a","b"],["aa","b","a","a","b"],["aa","b","aa","b"],["aa","baab"],["aabaa","b"]]

So, we need to split the given string into however many parts as we want, but each partition should be a palindrome, and we need to return all such partitions.

When a problem can be broken down into smaller subproblems that can be solved independently, and when there are many possible solutions, but only a few that are valid, backtracking is the optimal approach to solve it.

In this problem, we need to check all possible sets of partitions that can be produced from the given string and add it to the answer if all partitions of the set are palindromes.

Let's see exactly how we can apply backtracking to solve this problem.

Intuition

We need to check all possible sets of partitions of the string. We can start by iterating over the string from an index say start inside a recursive function. For each subsequent index, we check if the string s.substr(start, i - start + 1) is a palindrome. If it is, then we push it to an array curr and recursively call the backtracking function with the start variable set to i + 1. After that we backtrack by removing the string from curr and moving on to the next index.

The base condition for this recursive function would be when start >= s.size(), that is, when we reach the end of the array.

Here's the algorithm we'll be using.

Algorithm

1. Initialise vector<string> curr to store the current partitions of the string and vector<vector<string>> ans to store all valid palindromic partitions.

2. Declare a function void helper(string s, vector<vector<string>> &ans, vector<string> &curr, int start) that will perform the backtracking.

3. Declare a function isPalin(string s, int low, int high) that checks whether the given string between indexes low and high is a palindrome or not.

4. Inside helper, do the following:

   1. If the index start is greater or equal to the length of the string, insert the partitions inside curr into ans and exit the function. This will be the base condition for the recursion.

   2. If start is less than the length of the string, loop through the string starting from start until the end.

   3. If the substring formed from start to the current index i is a palindrome, we push this substring to curr and recursively call the helper function with the start parameter set to i + 1.

   4. Then, we remove the substring from curr , that is, we backtrack, and move on to the next index.

Try to code up this algorithm before moving on to the next section.

Coding Up The Solution

Here's the full solution to this problem.

class Solution {
public:
    //function to check if a string is a palindrome between indexes low and high
    bool isPalin(string s,int low,int high){
        while(low < high){
            if(s[low++] != s[high--]) return false;
        }
        return true;
    }
    //recursive function to find all palindromic partitions
    void helper(string s, vector<vector<string>> &ans, vector<string> &curr, int start){
        //base condition
        if(start >= s.size()) ans.push_back(curr);

        for(int i = start; i < s.length(); i++){
            if(isPalin(s,start,i)){
                //push current substring to curr
                curr.push_back(s.substr(start,i - start + 1));
                //recursive call
                helper(s,ans,curr,i+1);
                //backtrack
                curr.pop_back();
            }
        }

    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        vector<string> curr;

        helper(s, ans, curr, 0);
        return ans;
    }
};

That's all there is to this problem! Hope you had fun understanding this one. Backtracking is one of those topics that when you do finally start solving problems like these on your own, it'll give you a sense of satisfaction like no other.

Let me know if you have any doubts in the comments, and be sure to subscribe to my newsletter to keep up with my Leetcode struggles.

Cheers!