Loading page…
Practice problem · medium
A monitoring app shows each service as a strip of status codes, one letter per minute. The letter a means healthy, b means slow and c means down.
On a small screen the app trims a strip. A trim cuts a run of one letter from the front and a run of the same letter from the back. The app can trim again on what is left. You are asked how short a strip can get.
Write shortest_after_trimming(code).
code[i] is the status in minute i: the letter a, b or c.x. It removes a non-empty prefix made only of x and a non-empty suffix made only of x.Input: code = "aabcbaaa"
Output: 1Pointers lo and hi start at the two ends. While the letters at the ends match, each pointer skips the whole run of that letter.
| lo | hi | Ends | Skip | Letters left |
|---|---|---|---|---|
| 0 | 7 | a and a | front skips aa, back skips aaa |
bcb (minutes 2 to 4) |
| 2 | 4 | b and b | front skips b, back skips b |
c (minute 3) |
| 3 | 3 | the same minute | the walk stops | c |
The ends meet on a lone c. It has no partner at the other end, so it stays. The shortest length is 1.
Input: code = "ab"
Output: 2The ends a and b differ, so no trim is possible.
Input: code = "aaa"
Output: 0Trim the prefix aa and the suffix a. They do not overlap, and nothing is left.
1 ≤ code.length ≤ 100,000 (minutes in one strip)code[i] is one of a, b, cThe first attempt cuts one letter at a time and rebuilds the strip after every cut. A strip of 100,000 equal letters needs 100,000 rebuilds, and each one copies up to 100,000 letters. That is about n × n ÷ 2 = 5 × 10^9 copies, close to 50 seconds at 10^8 a second. A walk with one pointer at each end moves at most 100,000 steps in total.
The answer is at most 100,000, so it fits in a 32-bit integer.
shortest_after_trimming · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.