Palindrome Partitioning Problem

Problem Statement:

Given a string s, the task is to partition the string into all possible palindrome substrings. We need to find and return all possible valid partitions where each substring is a palindrome.

Approach:

1. ispalindrome Function:

The ispalindrome function checks whether a given substring of string s is a palindrome.

Parameters:

• s: The input string.
• start: The starting index of the substring.
• end: The ending index of the substring.

Implementation:

• This function uses a two-pointer approach to compare characters from both ends of the substring.
• If any characters don’t match, it returns false, indicating the substring is not a palindrome.
• If all characters match, it returns true and prints the palindrome substring.

2. calculate Function:

The calculate function recursively generates all valid partitions of the input string s.

Parameters:

• index: The current index in the string.
• t: A vector of vectors that stores the valid palindrome partitions.
• s: The input string.
• path: A vector that stores the current partition path.

Implementation:

• The function works recursively and explores all possible substrings starting from the index.
• If the substring from index to i is a palindrome, we add it to the path.
• The function then recursively calls itself with the updated index and the current path.
• If the index reaches the end of the string, we’ve found a valid partition, and we add it to the result (t).
• Backtracking is performed by removing the last added palindrome from the path.

3. partition Function:

This is the main function that initializes the process of palindrome partitioning.

Parameter:

• s: The input string.

Implementation:

• The function initializes an empty vector of vectors (t) to store the valid palindrome partitions.
• It also initializes an empty vector (path) to store the current partition path.
• The calculate function is called with initial parameters to start the recursive partition generation process.
• Finally, the function returns the vector t containing all valid palindrome partitions.

---

Test Cases

Test Case 1: Basic Case with Single Palindrome

Input:
s = "aab"

Output:
[["a", "a", "b"], ["aa", "b"]]

Explanation:
The string "aab" can be partitioned in two valid ways:

1. "a", "a", "b"
2. "aa", "b"

---

Test Case 2: String with All Palindromes

Input:
s = "a"

Output:
[["a"]]

Explanation:
The string "a" is already a palindrome, so the only partition is itself.

---

Test Case 3: String with Multiple Palindromes

Input:
s = "racecar"

Output:
[["r", "a", "c", "e", "c", "a", "r"], ["racecar"]]

Explanation:
The string "racecar" can be partitioned in two valid ways:

1. "r", "a", "c", "e", "c", "a", "r"
2. "racecar" (the whole string is a palindrome)

---

Test Case 4: No Palindrome Substring

Input:
s = "abc"

Output:
[["a", "b", "c"]]

Explanation:
Since no two characters form a valid palindrome substring except for the single characters, the only valid partition is each character individually.

---

Test Case 5: Larger Input with Palindromes

Input:
s = "aabb"

Output:
[["a", "a", "b", "b"], ["aa", "b", "b"], ["a", "a", "bb"]]

Explanation:
The string "aabb" can be partitioned into the following valid palindrome partitions:

1. "a", "a", "b", "b"
2. "aa", "b", "b"
3. "a", "a", "bb"

---

— Written by Saurabh Patil • B.Tech CSE • Software Developer