Smallest String and Regex
Regular expressions (abbreviated regex or regexp) are patterns which are used to represent a set of strings. A regex can be represented as a graph with multiple nodes. One of them is the start node and another one is the final node, and characters of regex can serve as edges.
Formally, a regex and the matching string abides by the following rules.
- Epsilon (): is used to represent a regular expression that matches an empty string. A string matches when "".
- Literal character: A single character, , is a regular expression. Any string where will match it. For this problem, will a lowercase latin letter .
- Concatenation: If and are regular expressions then is also a regular expression. A string matches if there exists two substrings and where and matches , and matches .
- Alternation (): If and are regular expressions then is also a regular expression. Any string which matches or will match .
- Kleene Star (): If is a regular expression then is also a regular expression. A string matches it if can be partitioned into zero or more substrings such that and each matches .
- Precedence Order: Kleene Star > Concatenation > Alternation
Sample Regex
Below is the graph for regex
Problem Statment
You are given a regex, , and an integer, . Find the length of the smallest string whose length is equal to or greater than , but not greater than , and matches regex .
Input Format
The first line of input contains an integer, , representing the number of test cases. Each test case consists of two lines. The first line will contain a non-negative integer representing the minimum length of the string to be searched, . The next line will contain a valid regular expression, .
Constraints
- will be a valid regular expression
- will consist of a lowercase latin character or any of { '(', ')', '*' , '|' }
Output Format
For each case, print the length of the smallest string matching regex and whose length is equal to or greater than , but not greater than . If no such string is possible, print "-1" (without quotes).
Sample Input
3
5
ab*(c|d)
5
aba
7
(ab|ba)*
Sample Output
5
-1
8
Explanation
Test Case #00
"ab*(c|d)" represents the set of strings where the first character is 'a', last character is either 'c' or 'd'. In between them there can be zero or more occurrences of 'b'. As we have to create a string of minimum length , we will add three 'b' in between them. Two possible solutions, with minimum length, are "abbbc" and "abbbd".Test Case #01
Since no string is possible of minimum length and matching regex "aba", we will print here.Test Case #02
"(ab|ba)*" represents an set of strings which is a concatenation of 0 or more "ab"/"ba". It will always be of even length.