Symmetric Substring Partitioning

Problem Statement

Symmetric Substring Partitioning Problem Description A publishing company wants to create special labels for its products that include a hidden symmetry. Each label is represented as a string composed of lowercase letters. The company believes that the attractiveness of a label increases if it can be divided into several contiguous parts wherein every part reads the same forward and backward. Your task is to determine the number of ways to partition the given label into one or more contiguous substrings such that each substring is symmetric (i.e., a palindrome). Every valid partition must cover the entire label without leaving any characters unassigned, and two partitions are considered different if the sets of cut indices between substrings differ. Input: A single string S which represents the label. This string consists only of lowercase alphabetical characters. Output: A single integer that represents the number of different ways to partition the string S into contiguous substrings