Nested ribbon depth
EasyOnline Assessment
Check how deeply a gift-wrap ribbon pattern is nested, and find where it goes wrong.
A pattern is a string. Round ribbons are written ( ... ) and square ribbons [ ... ]; lowercase letters are decoration and are ignored. A ribbon that is opened must be closed by a closer of the same kind, and ribbons must be closed in the reverse order they were opened (the innermost open ribbon first).
Walk through pattern from left to right, with positions numbered from 1:
- A pattern is fine if no closer arrives at a wrong moment and every ribbon is closed by the end. The depth at any moment is the number of ribbons currently open (of either kind). For a fine pattern, report the largest depth reached and the position of the first character at which that largest depth is reached.
- A pattern is broken when a closer arrives and there is no open ribbon, or the innermost open ribbon is of the other kind. Report the position of that first offending closer.
- If the whole pattern is read without such a mistake but some ribbons are still open at the end, it is also broken. Report the position of the earliest-opened ribbon that is still open.
Input: pattern, a string.
Output: [depth, position] for a fine pattern, [-1, position] for a broken one. A pattern with no ribbons at all (including the empty string) is fine with depth 0, and its answer is [0, 0].
Example 1
- Input:
- ["(a[b]c(d))"]
- Output:
- [2,3]
- Explanation
- Reading
(a[b]c(d)): the(at position 1 opens ribbon depth 1, the[at position 3 reaches depth 2 for the first time. Later the second(also reaches depth 2, but it is not the first time. Everything closes properly, so the answer is[2, 3].
Example 2
- Input:
- ["[(])"]
- Output:
- [-1,3]
- Explanation
- In
[(])the]at position 3 arrives while the innermost open ribbon is a round one(. A closer must match the kind of the innermost open ribbon, so position 3 is the first mistake:[-1, 3].
Example 3
- Input:
- ["(()["]
- Output:
- [-1,1]
- Explanation
(()[has 4 characters and ends with two ribbons still open: the(at position 1 (the outermost) and the[at position 4. The(at position 2 was closed at position 3. The earliest unclosed one is at position 1, so the answer is[-1, 1].
Constraints
0 <= pattern.length <= 200patterncontains only the characters(,),[,]and lowercase letters