Probe Echo Trimming Ledger
Minimum deletion cost to make each integer array prefix palindromic
A deep-space probe records a sequence of integer echo codes. Mission control wants to retain a symmetric sequence: its codes must read the same from left to right and from right to left.
You are given two arrays of equal length:
codes[i]is the code of readingi.eraseCosts[i]is the energy required to erase that reading.
Readings may be erased individually. The readings that remain keep their original relative order. An empty sequence and a sequence containing one reading are both considered symmetric.
For each nonempty prefix of codes, independently find the minimum total energy needed to erase readings so that the remaining sequence is symmetric.
Return an integer array ledger of the same length as codes, where ledger[r] is the minimum energy for the prefix consisting of readings 0 through r. Erasures chosen for one prefix do not affect any other prefix. If codes is empty, return an empty array.
Examples
Example 1
Input: codes = [4,4,9], eraseCosts = [6,2,3] Output: [0,0,3]
The first two prefixes are already symmetric. In the third prefix, the final code conflicts with the earlier codes, so erasing that final reading is cheaper than erasing both earlier readings.
Example 2
Input: codes = [5,-2,-2,5], eraseCosts = [9,1,4,7] Output: [0,1,5,0]
For the prefix ending at the third reading, either endpoint can be erased to leave a matching pair, and their erasure costs differ. The complete sequence is already symmetric and needs no erasures.
Example 3
Input: codes = [], eraseCosts = [] Output: []
There are no nonempty prefixes, so the ledger is empty.
Constraints
- 0 <= codes.length <= 1600
- eraseCosts.length == codes.length
- -10^9 <= codes[i] <= 10^9
- 0 <= eraseCosts[i] <= 10^6
Erasure costs belong to original reading indices, even when several readings have the same code. Only minimum energies are returned, so ties between different erasure choices do not require a tie-breaking rule.
Hints
Show hint 1Hint 1
Define a state for the minimum erasure energy needed to make the interval from index l through index r symmetric.
Show hint 2Hint 2
You may erase either endpoint. If their codes match, you may also retain both endpoints and solve only the interior. Process right endpoints in increasing order to obtain every requested prefix result.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also recover one optimal set of erased indices for the complete sequence?
- Can you compute the entire ledger with only O(n) auxiliary space while keeping O(n^2) running time?
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