Frontend School

Palindromic Partitions

DSA
medium

Palindromic Partitions

Medium
Recursion
Backtracking
String

Overview

At Netflix, robust text processing and pattern recognition are crucial for various applications, from content metadata analysis to search optimization and even subtitle synchronization. Identifying meaningful structures within text can help us categorize content, improve search relevance, or detect anomalies. This problem challenges you to find all ways to break down a given string into a sequence of substrings, where each substring itself is a palindrome. This task directly applies to advanced string parsing and text segmentation algorithms.

What you need to do / Task

Implement a function partition that takes a string s and returns all possible palindromic partitions of s. A palindromic partition is a list of substrings, where concatenating them forms the original string s, and every substring in the list is a palindrome.

Input & output

  • Input: s (string)
    • The input string consisting of lowercase English letters.
  • Output: string[][]
    • An array of arrays of strings. Each inner array represents a valid palindromic partition of s.

Clarifications

  • An empty string "" should result in an empty list of partitions [].
  • A single character string, e.g., "a", is a palindrome and its only partition is [["a"]].
  • The order of partitions in the output array does not matter, but the order of substrings within each partition must be preserved to form the original string.

Examples

1

Example 1

Input:

s = "aab"

Output:

[["a","a","b"], ["aa","b"]]

Note:

For "aab":

  1. Partition "a", "a", "b". All are palindromes.
  2. Partition "aa", "b". Both are palindromes.
2

Example 2

Input:

s = "a"

Output:

[["a"]]

Note:

For "a":

  1. Partition "a". It is a palindrome.
3

Example 3

Input:

s = "bb"

Output:

[["b","b"], ["bb"]]

Note:

For "bb":

  1. Partition "b", "b". Both are palindromes.
  2. Partition "bb". It is a palindrome.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 16
  • s consists only of lowercase English letters.

Out of scope

  • Input validation (assume s will always meet the constraints).
  • Optimizing for extremely long strings (e.g., pre-computing all palindromic substrings using dynamic programming for s.length > 1000). For the given constraints, a simple isPalindrome check per substring is acceptable.

What interviewers evaluate

  • Correctness of the recursive (backtracking) algorithm to explore all possible partitions.
  • Efficient and accurate identification of palindromic substrings.
  • Proper handling of base cases and termination conditions for the recursion.
  • Clarity, readability, and maintainability of the code structure.

Loading editor...