Palindromic Partitioning

Given a string ‘str’. Find the minimum number of partitions to make in the string such that every partition of the string is a palindrome.

Given a string, make cuts in that string to make partitions containing substrings with size at least 1, and also each partition is a palindrome. For example, consider “AACCB” we can make a valid partition like A | A | CC | B. Among all such valid partitions, return the minimum number of cuts to be made such that the resulting substrings in the partitions are palindromes.

The minimum number of cuts for the above example will be AA | CC | B. i.e 2 cuts

Note :
1) We can partition the string after the first index and before the last index.

2) Each substring after partition must be a palindrome.

3) For a string of length ‘n’, if the string is a palindrome, then a minimum 0 cuts are needed.  

4) If the string contains all different characters, then ‘n-1’ cuts are needed.

5) The string consists of upper case English alphabets only with no spaces.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

Each test case on a separate line contains a string ‘str’ denoting the string to be partitioned.
Output Format :
 For each test case, return the minimum number of cuts to be done so that each partitioned substring is a palindrome.
Constraints :
1 <= T <= 50
1 <= length(string) <= 100


Where ‘T’ is the total number of test cases, ‘length(string)’ denotes the length of the string.

Time limit: 1 second
CodingNinjas
author
2y
Brute Force Approach
  • This is a recursive approach.
  • We can break the problem into a set of related subproblems which partition the given string in such a way that yields the lowest possible total cuts.
  • In...read more
CodingNinjas
author
2y
Dynamic Programming Approach

Following is a recursion tree for the string “ABC”

Refer Above Image

We can observe that the problem has optimal substructure and overlapping subproblems and hence can be sol...read more

CodingNinjas
author
2y
Highly Optimised Dynamic Programming Approach

In the previous approach, we calculated the minimum cut while finding all palindromic substring. If we find all palindromic substrings first and then calcu...read more

Add answer anonymously...
Adobe Software Quality Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions
Get AmbitionBox app

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter