Longest clean markup run: hints, no solution
Hard · Stack
A markup linter receives a line already split into events. An opening event is a plus sign followed by a tag name, a closing event is a minus sign followed by a tag name, and a self-closing event is a star followed by a tag name; a self-closing event stands alone and needs no partner.
A run is a block of consecutive events that is properly nested: every opening event in it is closed inside it by an event of the same name, each close matches the most recently opened tag that is still open, and self-closing events may appear anywhere. A single self-closing event is a valid run, and the empty run is allowed.
Return the length of the longest run in the line, or 0 if there is none. Do it in linear time; trying every start position is too slow for long lines.
Examples
- Input
- tokens = ["+a", "+b", "-b", "-a", "-c"]
- Output
- 4
- Note
- The run plus a, plus b, minus b, minus a has length 4. The final minus c has no opener.
- Input
- tokens = ["*br", "+a", "-b", "+p", "*hr", "-p", "+q"]
- Output
- 3
- Note
- The best run is plus p, star hr, minus p. The mismatched minus b breaks everything before it.
Constraints
- 0 <= tokens.length <= 120000
- Each event is +, - or * followed by 1 to 10 lowercase letters or digits
- Tag names compare exactly
Hint 1: a nudge
Suppose a run ends at some event. What decides how far to the left it can start, and what would make a longer start impossible?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.