401927: GYM100584 D Balanced strings

Memory Limit：256 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

D. Balanced stringstime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

We call a string balanced if all its characters (those which occur in it at least once) occur in it an equal number of times. For example, aaaaa, badcx, bbaaab are balanced strings. However, abacb isn't a balanced string.

Given a string, find its longest (continuous) balanced substring.

The substring we're looking for doesn't have to contain all characters which occur in the original string. For example, the correct answer for cbababac is the substring bababa.

Input

The input consists of a single string of lowercase letters of English alphabet. The string has length N and the characters are indexed from 0 to N - 1.

Output

Print a single line containing two space-separated integers: indices of the character by which the substring we're looking for starts and the one by which it ends. If there are multiple optimal solutions, find the one that starts the earliest.

ExamplesInput
baab
Output
0 3
Input
baaab
Output
1 3
Input
cbababac
Output
1 6
Input
cbabadbabae
Output
1 4
Note

There are 10 sets of tests, in which the following restrictions hold:

Set(s) no.Length of inputSet of letters used
11 ≤ N ≤ 20[ab]
21 ≤ N ≤ 1000[ab]
3-41 ≤ N ≤ 1000[abcdefgh]
51 ≤ N ≤ 105[ab]
61 ≤ N ≤ 105[abc] (the optimal solution doesn't use all three)
71 ≤ N ≤ 105[abc]
8-101 ≤ N ≤ 5·104[abcde]

Source/Category

加入题单

上一题 下一题 算法标签：