Statistics

Problem Statement for "BearPair"

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 String s. If Limak cannot choose any integers with the required properties, return -1. Otherwise, return the largest possible difference between i and j.

Definition

Class:
BearPair
Method:
bigDistance
Parameters:
String
Returns:
int
Method signature:
int bigDistance(String s)
(be sure your method is public)

Constraints

  • s will have between 2 and 50 characters, inclusive.
  • Each character in s will be a lowercase English letter ('a' - 'z').

Examples

  1. "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.

  2. "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.

  3. "oooohyeahpotato"

    Returns: 13

  4. "zzzzzzzzzzzzzzzzzzzzz"

    Returns: -1

    Here, Limak can't choose two indices with different letters.

  5. "qw"

    Returns: 1

  6. "xxyyxyxyyyyyyxxxyxyxxxyxyxyyyyyxxxxxxyyyyyyyyxxxxx"

    Returns: 47

  7. "qqqqqqqqqqqpasbzqcefrbmzbeeklwxjuqahqq"

    Returns: 35

  8. "piiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii"

    Returns: 38

  9. "waqunmledulebqqeesuhpctgdewwwww"

    Returns: 29

  10. "wwwwwwwwwbtvyqjfjdwwwwwwwwwwwwww"

    Returns: 22

  11. "ssssssssssss"

    Returns: -1

  12. "aa"

    Returns: -1

  13. "zz"

    Returns: -1

  14. "yz"

    Returns: 1

  15. "yz"

    Returns: 1

  16. "aba"

    Returns: 1

  17. "abb"

    Returns: 2

  18. "aab"

    Returns: 2

  19. "aaa"

    Returns: -1

  20. "kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk"

    Returns: -1

  21. "vijjv"

    Returns: 3

  22. "qqqqqqqqqqqqkruagjeqftqqqqqqqqqqq"

    Returns: 21

  23. "srclwgmobsdiqppxjbtlkpaouzxmvvnhvmmmmmmmmmmmmm"

    Returns: 45

  24. "ooooonnhfcznftrtgxptbjoooooooooooooo"

    Returns: 30

  25. "bzmbr"

    Returns: 4

  26. "pp"

    Returns: -1

  27. "ewrpjvwkwinnoupgtrbvijxnaquwluqpqhhzedmbnbqbvikpzl"

    Returns: 49

  28. "qqqqqepaaxkzswfnssbfxkdbmtedgtcphuseeqqbeludelmnuq"

    Returns: 48

  29. "bbbbbbssxjzekhgixvzenwjpxtgqibrsahjtqbbbbbbbbbbbbb"

    Returns: 43

  30. "bb"

    Returns: -1

  31. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

    Returns: -1

  32. "miraupmomiqa"

    Returns: 11

  33. "yvo"

    Returns: 2

  34. "vvvv"

    Returns: -1

  35. "pp"

    Returns: -1

  36. "tj"

    Returns: 1

  37. "ttpoozilzpxtjebarvgiylurwjjpoutfeodby"

    Returns: 36

  38. "johggvonllrwrdizeroqzpvbnkoaqvlagjstibupsomswqjoq"

    Returns: 48

  39. "ycjedfvwygrctuytlujzunyjvpumimquxdggcccccccccc"

    Returns: 45

  40. "aaaaazzzzzzzzzaaaaaaaaaaaaaaaa"

    Returns: 24

  41. "zzzzzzzzzzzaaaaaaaazzzzzzzzzzzzzz"

    Returns: 21

  42. "zyz"

    Returns: 1

  43. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: -1

  44. "abaaa"

    Returns: 3

  45. "abaaaaaaaa"

    Returns: 8

  46. "aaaaaaaabbba"

    Returns: 10

  47. "xxxxxxxxxxxxy"

    Returns: 12

  48. "abz"

    Returns: 2

  49. "bbbabbbbbbbbbb"

    Returns: 10

  50. "abcdab"

    Returns: 5

  51. "zzzazz"

    Returns: 3

  52. "aaaa"

    Returns: -1

  53. "aaaaa"

    Returns: -1

  54. "bbbbbbbbbbbbbbbbbab"

    Returns: 17

  55. "aaaaaa"

    Returns: -1

  56. "ab"

    Returns: 1

  57. "adbaaa"

    Returns: 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: