String Theory
InterviewTime limit2sMemory limit512 MB
Given alternating runs of quote characters, find the largest k for which the whole string is a k-quotation.
- Level
Medium5 of 10
- Topics
- Dynamic programming, String, Intervals
- Solved
- No attempts yet
Problem
Nested quotations are useful in literature with a layered narrative, and in programming languages as well. Using a different quotation mark at every nesting level makes the levels obvious, but there is another way. A -quotation marks the nesting level by repeating one single quote character, and it is defined as follows.
A 1-quotation is a string that starts with a quote character, ends with another quote character, and contains no quote character in between. This is the ordinary, unnested quotation. For example, 'this is a string' is a 1-quotation.
For , a -quotation is a string that starts with quote characters, ends with another quote characters, and holds a nested string in between. The nested string is a non-empty sequence of -quotations, and any number of non-quote characters may appear before them, between them, and after them. For example, ''All 'work' and no 'play''' is a 2-quotation.
You are given a description of a string. Find its largest possible nesting level.
Input
The first line contains an integer (). The second line contains integers (), which describe a string as follows. The string starts with quote characters, followed by a positive number of non-quote characters, followed by quote characters, followed by a positive number of non-quote characters, and so on, until the string ends with quote characters.
Output
Print the largest such that the described string is a -quotation. If no such exists, print no quotation instead.