Substring and five rules
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Given a string S. You need to find a substring which satisfies the following conditions and output its start and end positions in the string S.
- Has exactly x different characters in it.
- Length of substring is atleast minLength and atmost maxLength.
- substring's start position is greater than or equal to L.
- substring's end position is less than or equal to R.
If there are multiple substrings that satisfy above conditions, choose the one that has least start position. If there are still multiple substrings, choose the one that has least end position. See output section for more details
First line of input contains the string S
The second line of the input contains an integer Q denoting the number of queries.
Only line of each query contains 5 space separated integers, x, minLength, maxLength, L, R
For each query, output one line with 2 space separated integers, start and end positions of substring in S. If there is no valid solution output "-1 -1" instead
- 1 ≤ |S| (Length of S) ≤ 10^5
- S contains only lower case english alphabet ('a' - 'z')
- 1 ≤ Q ≤ 10^5
- 1 ≤ x ≤ 26
- 1 ≤ minLength ≤ maxLength ≤ |S|
- 0 ≤ L ≤ R ≤ |S|-1
Input abcc 3 2 1 3 0 3 2 3 3 0 3 1 2 2 0 2 Output 0 1 1 3 -1 -1
We need a substring with 2 different characters, of length 1 or 2 or 3 and in between S[0..3].
S[0..1] = "ab", which has 2 different characters, length 2, and is in between S[0..3]
Here we need the length to be 3.
S[1..3] = "bcc", has 2 different characters, length 3, and is in between S[0..3]
|Tags||anudeep2011, cook51, greedy, hard, segment-tree, two-pointers|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.