BearPair
SRM 680 · 2016-01-04 · by Errichto
Problem Statement
Bear Limak loves algorithms, especially the ones with words and strings.
Limak's friend recently entered a programming competition and wrote a program. The program contains a string constant s. Limak would now like to challenge the program by making it exceed the time limit. To do that, he must find two different characters in s that are as far apart as possible.
Formally, Limak must find two integers i and j with the following properties:
- Both i and j must be valid indices into s. That is, both numbers must be between 0 and n-1, inclusive, where n is the length of s.
- The characters s[i] and s[j] must be different.
- The difference between i and j must be as large as possible.
You are given the
Constraints
- s will have between 2 and 50 characters, inclusive.
- Each character in s will be a lowercase English letter ('a' - 'z').
"bear" Returns: 3
Limak can choose the (0-based) indices 0 and 3. We have s[0]='b' and s[3]='r', which are indeed two different letters. The difference between the two indices is 3-0 = 3.
"abcba" Returns: 3
Here, one optimal solution is for Limak to choose the indices 1 and 4 (corresponding to 'b' and 'a', respectively). Another optimal solution is to choose indices 0 and 3 (letters 'a' and 'b'). In both cases the difference is 3.
"oooohyeahpotato" Returns: 13
"zzzzzzzzzzzzzzzzzzzzz" Returns: -1
Here, Limak can't choose two indices with different letters.
"qw" Returns: 1
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearPair with a public method int bigDistance(string s) · 57 test cases · 2 s / 256 MB per case