Frontend School

Palindromic Partitioning with Character Diversity

DSA
hard

Palindromic Partitioning with Character Diversity

Hard
Backtracking
String
Palindrome

Overview

In text processing and content analysis, understanding the structural properties of strings is crucial. This problem challenges you to segment a given string into palindromic substrings, but with an additional constraint: the overall diversity of characters across all segments must meet a specific threshold. This task mirrors real-world scenarios where content needs to be broken down into meaningful, self-contained units while adhering to global compositional rules.

What you need to do / Task

Your task is to implement a function findAllPalindromicPartitionsWithDiversity that takes a string s and an integer k. The function should find all possible ways to partition s into one or more non-empty palindromic substrings. From these partitions, you must return only those where the total number of distinct characters present across all substrings in the partition is exactly k.

For example, if a partition is ["a", "aa", "b"], the distinct characters are 'a' and 'b', so the count is 2.

Input & output

Function Signature:

function findAllPalindromicPartitionsWithDiversity(s: string, k: number): string[][]

Input:

  • s: A non-empty string consisting of lowercase English letters.
  • k: An integer representing the required number of distinct characters in a valid partition.

Output:

  • A string[][] representing a list of all valid partitions. Each inner string[] is a single valid partition. The order of partitions in the outer list, and the order of substrings within each partition, does not matter.

Clarifications

  • An empty string s is not expected as per constraints.
  • If no valid partitions are found, return an empty string[][].
  • A single character is considered a palindrome (e.g., "a").
  • The string s will only contain lowercase English letters ('a' through 'z').

Examples

1

Example 1

Input:

s = "aab", k = 2

Output:

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

Note:

For partition ["a","a","b"], distinct characters are {'a', 'b'}, count = 2. Matches k. For partition ["aa","b"], distinct characters are {'a', 'b'}, count = 2. Matches k.

2

Example 2

Input:

s = "abacaba", k = 3

Output:

[["a","b","a","c","a","b","a"],["a","b","acaba"],["a","bacab","a"],["aba","c","aba"],["abacaba"]]

Note:

All listed partitions have exactly 3 distinct characters ('a', 'b', 'c'). For example, ["a","b","acaba"]: characters are 'a', 'b', 'a', 'c', 'a', 'b', 'a'. Distinct: {'a', 'b', 'c'}, count = 3.

3

Example 3

Input:

s = "abc", k = 1

Output:

[]

Note:

The only palindromic partition is ["a","b","c"]. The distinct characters are {'a', 'b', 'c'}, count = 3. This does not match k=1. No valid partitions found.

Constraints

Constraints & assumptions

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

What interviewers evaluate

  • Correctness: The solution must correctly identify all valid palindromic partitions and accurately filter them based on the distinct character count k.
  • Efficiency: The approach should be efficient enough to pass within typical time limits for the given constraints, demonstrating an understanding of how to optimize palindrome checks (e.g., dynamic programming or memoization).
  • Algorithm Design: Clear application of backtracking principles to explore all possible partitions without redundant computations.
  • Code Quality: Well-structured, readable code with appropriate variable names and comments.

Loading editor...