Statistics

Problem Statement for "SuffixArrayDiv2"

Problem Statement

Suffix number i of a string S is the suffix that starts with the character S[i]. For example, for S="abcde" suffix 0 is "abcde" and suffix 3 is "de".

The suffix array of a string S is defined as the permutation of suffix numbers that corresponds to their lexicographic order. For example, suppose that S="abca". If we order all suffixes of S lexicographically, we get the following: "a" < "abca" < "bca" < "ca". The corresponding suffix numbers are 3, 0, 1, and 2, in this order. Thus, for this string S the suffix array would be {3, 0, 1, 2}. Note that the length of a suffix array is the same as the length of the original string.

In this problem, we will only consider strings of lowercase English letters ('a'-'z'). You are given a String s. We are interested in a string t that is lexicographically smaller than s but has exactly the same suffix array. Return "Exists" if at least one such string t exists, and "Does not exist" otherwise.

Definition

Class:
SuffixArrayDiv2
Method:
smallerOne
Parameters:
String
Returns:
String
Method signature:
String smallerOne(String s)
(be sure your method is public)

Notes

  • Given two different strings A and B of the same length, A is lexicographically smaller than B if we have A[i] < B[i] for the smallest i such that A[i] and B[i] differ.

Constraints

  • s will contain between 1 and 50 elements, inclusive.
  • Each element in s will be a lowercase letter ('a'-'z').

Examples

  1. "abca"

    Returns: "Exists"

    For example, "aaqa" < "abca" but their suffix arrays are the same.

  2. "bbbb"

    Returns: "Exists"

    Obviously, one of the strings smaller than "bbbb" with the same suffix array is "aaaa".

  3. "aaaa"

    Returns: "Does not exist"

    The string "aaaa" is already the lexicographically smallest 4-letter string.

  4. "examplesareveryweakthinktwicebeforesubmit"

    Returns: "Exists"

  5. "b"

    Returns: "Exists"

  6. "atgctubcwlroomkowbvlbleofqujtykqa"

    Returns: "Exists"

  7. "beefgdgaadficdgchfehcfaaifbafb"

    Returns: "Does not exist"

  8. "fgqllpllcahbdjoqkmhoagdhmokjibfdcmhclkfpqkhc"

    Returns: "Exists"

  9. "bbbaaaccacacccbbabccaacbbcbbbaccbacabacacbccbbccab"

    Returns: "Does not exist"

  10. "cababacacbcaccbccccabcbccacccccbbbab"

    Returns: "Does not exist"

  11. "ekdcipkgojljqcnnjkmrejnbellnircpejanmhpac"

    Returns: "Exists"

  12. "bccebcklandbdkjeeakdhgligmngfaiiamnacbbdi"

    Returns: "Exists"

  13. "bcdcddeafdaeecafcaddccefccbaabccbce"

    Returns: "Does not exist"

  14. "acbnihbfgoolgjedggk"

    Returns: "Exists"

  15. "caacbaa"

    Returns: "Exists"

  16. "bbccebdebebbcaacdeed"

    Returns: "Does not exist"

  17. "thdddapjpnrcuddxuylsqipnfwdeppmepzea"

    Returns: "Exists"

  18. "bbbccacaaccbbccaababcacccbcaacaaccbbabccacacbab"

    Returns: "Does not exist"

  19. "aaaaaaaaaaaaaaaaaaaaaa"

    Returns: "Does not exist"

  20. "mmfkbfkhijlljbkcbmbleheckmelbiicjdllmf"

    Returns: "Exists"

  21. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: "Does not exist"

  22. "gvaribicppg"

    Returns: "Exists"

  23. "ccbbccbdabdacaabaccbcccbbadbdba"

    Returns: "Does not exist"

  24. "daddcecdbbcbeadcaebaaeccedbddcdadbdacdebdbdd"

    Returns: "Does not exist"

  25. "lkjdpp"

    Returns: "Exists"

  26. "onglrrrmimqoejgmjcdnjrspcaafijmkjsmkngd"

    Returns: "Exists"

  27. "bonpnidbmeqctoekgatrsqhmltislfgbfcdh"

    Returns: "Exists"

  28. "dtui"

    Returns: "Exists"

  29. "wwrchtepph"

    Returns: "Exists"

  30. "abbaabbaaabababaabbbbbabbbbbababbabbabaabababbaabb"

    Returns: "Does not exist"

  31. "igiijmgjhbmfh"

    Returns: "Exists"

  32. "cmffckalghmgcjkjfimiglaekbab"

    Returns: "Exists"

  33. "qfhbjqsdnnoehpaeamlhsocjqjrrlapuelaknejtmmaks"

    Returns: "Exists"

  34. "fbljlkdnnaeaptkjlzmv"

    Returns: "Exists"

  35. "ebfbdgiiciebbicabgfdeac"

    Returns: "Exists"

  36. "ccdbaebeaacbbaccdcaeaecbcdddcdacecabb"

    Returns: "Does not exist"

  37. "xaplcmeeiunobkwnehhdgnsowmlfnn"

    Returns: "Exists"

  38. "jhbjkkjdkjbijfe"

    Returns: "Exists"

  39. "dcggegfgebafddfbcdagafca"

    Returns: "Does not exist"

  40. "pbhjedr"

    Returns: "Exists"

  41. "mfbnlfhfcigncmbjedabed"

    Returns: "Exists"

  42. "qlensmrwsnlkpvtdectownnutg"

    Returns: "Exists"

  43. "bd"

    Returns: "Exists"

  44. "skirjrbobmiscnjqetetdfmn"

    Returns: "Exists"

  45. "agfcbkajdaebfmbdhcfkbhbmbj"

    Returns: "Exists"

  46. "pppfgmgguequrtecfbnqkjopbha"

    Returns: "Exists"

  47. "bcbdeaedceedabaebedbdcacedced"

    Returns: "Does not exist"

  48. "mlkilehfaljaibmabhabkjal"

    Returns: "Exists"

  49. "bbnelcjqcigsdajojgerfegafcvjffcrblpfbtmbodn"

    Returns: "Exists"

  50. "ighbbfifbgabhebcfhijdajcdihbfjfgaigjed"

    Returns: "Does not exist"

  51. "inmforrpdambgb"

    Returns: "Exists"

  52. "defcnlkcaabecdjabegfcalgaldccencekgmkmmcmmhg"

    Returns: "Exists"

  53. "cdddfefdaebgbgacadbebfdeebfaecgacacdfedaffebeebc"

    Returns: "Does not exist"

  54. "onpmnjldjbkdbljpqpficfo"

    Returns: "Exists"

  55. "odeikjbigipjnj"

    Returns: "Exists"

  56. "aleclmbcngkiihfinbmgbgdidjmelofja"

    Returns: "Does not exist"

  57. "beefgdgaadficdgchfehcfaaifbafb"

    Returns: "Does not exist"

  58. "efnjjmjjcagbdhlnikglafdgklihhbedckgcjiemnigc"

    Returns: "Does not exist"

  59. "bbbaaaccacacccbbabccaacbbcbbbaccbacabacacbccbbccab"

    Returns: "Does not exist"

  60. "cababacacbcaccbccccabcbccacccccbbbab"

    Returns: "Does not exist"

  61. "dfdcdkfdjegelciiefhldeibdggidlckdeaihdkac"

    Returns: "Does not exist"

  62. "bccebcjkaldbdjieeajdgfkhfklffahhaklacbbdh"

    Returns: "Does not exist"

  63. "bcdcddeafdaeecafcaddccefccbaabccbce"

    Returns: "Does not exist"

  64. "abageeacdgggdfcbddg"

    Returns: "Does not exist"

  65. "baabbaa"

    Returns: "Does not exist"

  66. "bbccebdebebbcaacdeed"

    Returns: "Does not exist"

  67. "idbbbafdfehajbbkjldhgdfeckbcffecfmca"

    Returns: "Does not exist"

  68. "bbbccacaaccbbccaababcacccbcaacaaccbbabccacacbab"

    Returns: "Does not exist"

  69. "aaaaaaaaaaaaaaaaaaaaaa"

    Returns: "Does not exist"

  70. "jjdhadhefgiigahbajaicecbhjciaffbgbiijd"

    Returns: "Does not exist"

  71. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: "Does not exist"

  72. "cfaedbdbddc"

    Returns: "Does not exist"

  73. "ccbbccbdabdacaabaccbcccbbadbdba"

    Returns: "Does not exist"

  74. "daddcecdbbcbeadcaebaaeccedbddcdadbdacdebdbdd"

    Returns: "Does not exist"

  75. "bbbacc"

    Returns: "Does not exist"

  76. "lkfinnnjgjmldhfjhbckhnombaaeghjihojikfc"

    Returns: "Does not exist"

  77. "bmlnlhdbkdocqmdifaqopogkjqhpjefbecdg"

    Returns: "Does not exist"

  78. "abcb"

    Returns: "Does not exist"

  79. "dddabdaccb"

    Returns: "Does not exist"

  80. "abbaabbaaabababaabbbbbabbbbbababbabbabaabababbaabb"

    Returns: "Does not exist"

  81. "cbccdebdcaebc"

    Returns: "Does not exist"

  82. "bjddbhaieejebghgdfjfeiachbab"

    Returns: "Does not exist"

  83. "nefbgnpckkldfmadajifplcgngooiamrdiahkdgqjjahp"

    Returns: "Does not exist"

  84. "cbecedbggacaghdceifi"

    Returns: "Does not exist"

  85. "ebfbdfggcgebbgcabffdeac"

    Returns: "Does not exist"

  86. "ccdbaebeaacbbaccdcaeaecbcdddcdacecabb"

    Returns: "Does not exist"

  87. "majfbgddekhibelhdeecdhjilgfdhh"

    Returns: "Does not exist"

  88. "dcadeedaedacdbb"

    Returns: "Does not exist"

  89. "dcggegfgebafddfbcdagafca"

    Returns: "Does not exist"

  90. "dabcbae"

    Returns: "Does not exist"

  91. "gdahfdedbedhbgafccaacc"

    Returns: "Does not exist"

  92. "hecfiehlifedgkjbcajflffjjd"

    Returns: "Does not exist"

  93. "ab"

    Returns: "Does not exist"

  94. "jfdieiahafdjbgehckckcdfg"

    Returns: "Does not exist"

  95. "afecbiahdaebejbdgceibgbjbh"

    Returns: "Does not exist"

  96. "iiiddgddlcjlklcbdagjfehiaea"

    Returns: "Does not exist"

  97. "bcbdeaedceedabaebedbdcacedced"

    Returns: "Does not exist"

  98. "ihgfhcedahgafbiabeabggah"

    Returns: "Does not exist"

  99. "bblejciochgqdaimigepfegafcriffcpbjnfbqkbmdl"

    Returns: "Does not exist"

  100. "ighbbfifbgabhebcfhijdajcdihbfjfgaigjed"

    Returns: "Does not exist"

  101. "deecefffcaebdb"

    Returns: "Does not exist"

  102. "defcljicaabecdiabegfcajgajdccelceigkikkckkhg"

    Returns: "Does not exist"

  103. "cdddfefdaebgbgacadbebfdeebfaecgacacdfedaffebeebc"

    Returns: "Does not exist"

  104. "ihjghfgcfagcagfjkjdebdi"

    Returns: "Does not exist"

  105. "gbbcedacbcgdfd"

    Returns: "Does not exist"

  106. "aba"

    Returns: "Does not exist"

  107. "aaab"

    Returns: "Does not exist"

  108. "abaa"

    Returns: "Does not exist"

  109. "aaba"

    Returns: "Does not exist"

  110. "aab"

    Returns: "Does not exist"

  111. "bb"

    Returns: "Exists"

  112. "acbca"

    Returns: "Does not exist"

  113. "aaac"

    Returns: "Exists"

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: