ORIGINAL CODING QUESTION

Minimum mirrored partition cuts

Partition the glyph sequence into contiguous palindromes. Return the fewest cuts between parts.

Open practice workspace

Original exercise · hard. Editorial role relevance does not imply a company has asked this question.

Input and output

n, then n integer values. Print one integer as described.

Constraints

1 ≤ n ≤ 30; each glyph is an integer in [0,25]. Equal integers mean equal characters.

Example 1

Input

3 0 0 1

Output

Partition 0,0 | 1 needs one cut.

Example 2

Input

3 0 1 0

Output

The whole sequence needs zero cuts.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

First identify which spans are palindromes.

Hint 2

Let dp[i] count the fewest pieces for a prefix.

Hint 3

A palindrome suffix extends an optimal shorter prefix; convert pieces to cuts.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →