Mirrored Cue Sessions
All string splits into k palindromic substrings, as exclusive end indices
A music streaming service stores an instrumental preview as a string cues. Each lowercase letter identifies the instrument heard at one cue position.
The service wants to split the entire preview into exactly clips nonempty, contiguous clips. Within each clip, the cue sequence must read the same forward and backward. No cue may be skipped or shared between clips.
Return every valid split as a list of exclusive ending positions. If a split is represented by [e1, e2, ..., ek], its clips are cues[0:e1], cues[e1:e2], and so on, with ek equal to the length of cues. Positions are zero-based, and each ending position is excluded from its clip.
Return the split lists in lexicographically increasing order: compare their first differing ending positions, and place the list with the smaller position first.
If no valid split exists, return an empty list. An empty preview has exactly one split into zero clips, represented by an empty list, so that case returns [[]].
Examples
Example 1
Input: cues = "abacdc", clips = 2 Output: [[3,6]]
For `abacdc` and two clips, the split between `aba` and `cdc` is valid because both clips read identically in either direction. No other two-clip split satisfies the rule.
Example 2
Input: cues = "aaaa", clips = 2 Output: [[1,4],[2,4],[3,4]]
Every nonempty substring of `aaaa` is mirrored. With two clips, any of the three internal boundaries is valid. The splits are ordered by their first ending position.
Example 3
Input: cues = "", clips = 0 Output: [[]]
The empty preview requires no clips. Its single valid split contains no ending positions.
Constraints
- 0 <= cues.length <= 18
- cues contains only lowercase English letters.
- 0 <= clips <= 18
Each ending-position list uniquely identifies a split. Different positions remain distinct even when their clip contents are identical. The answer can be exponentially large; the length limit is intentionally small.
Hints
Show hint 1Hint 1
Precompute whether each substring reads the same forward and backward.
Show hint 2Hint 2
Build the ending positions from left to right. A suffix-feasibility table can tell you whether the remaining suffix can form the remaining number of clips.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you count valid splits without constructing their ending-position lists?
- How would you return only the lexicographically smallest valid split?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem