Statistics

Problem Statement for "LexOrder"

Problem Statement

In this problem, all strings are strings of lowercase English letters ('a'-'z').

You are given the Strings A and B such that A < B. If there is a string C such that A < C < B, return any such string. (The returned string C must have at most 50 characters, and each character of C must be a lowercase English letter.) If there is no such string C, return the string "IMPOSSIBLE" instead.

 

Below, we define how to compare two strings. This definition is the standard one and we include it just to have a complete, self-contained problem statement. If you already know how string comparison works, you do not have to read it.

Suppose S and T are two distinct strings. We say that S is smaller than T in lexicographic order (denoted S < T) if:

  1. either S is a proper prefix of T,
  2. or there is some i >= 0 such that:
    1. the first i characters of S are the same as the first i characters of T
    2. the next character of S is smaller than the next character of T

For example:

  • "car" < "careful" because "car" is a proper prefix of "careful"
  • "dog" < "donut" because the first two characters of both strings are the same ("do") and 'g' is smaller than 'n'.

Definition

Class:
LexOrder
Method:
between
Parameters:
String, String
Returns:
String
Method signature:
String between(String A, String B)
(be sure your method is public)

Notes

  • The statements "character x is smaller than character y", "character x is earlier in the alphabet than character y", and "character x has a smaller ASCII code than character y" are equivalent.
  • The return value is case-sensitive. The string IMPOSSIBLE must be in all-uppercase.

Constraints

  • A will have between 1 and 10 characters, inclusive.
  • B will have between 1 and 10 characters, inclusive.
  • Each character of A and B will be a lowercase English letter ('a'-'z').
  • A will be lexicographically smaller than B.

Examples

  1. "car"

    "dog"

    Returns: "careful"

    Other valid return values include "ceiling", "catastrophiccancellation", "darling", "do", and "dododododo".

  2. "car"

    "cat"

    Returns: "cash"

  3. "abcdefghij"

    "abcdefghik"

    Returns: "abcdefghijklmnopqrst"

    Note that the input strings always have at most 10 characters but the string you return may be longer (up to 50 characters).

  4. "man"

    "mana"

    Returns: "IMPOSSIBLE"

  5. "a"

    "ab"

    Returns: "aa"

  6. "a"

    "aaa"

    Returns: "aa"

  7. "zumba"

    "zumbaa"

    Returns: "IMPOSSIBLE"

  8. "zumba"

    "zumbazumba"

    Returns: "zumbaa"

  9. "cnrosiq"

    "cnrosmtb"

    Returns: "cnrosiqa"

  10. "vadaizh"

    "vadaizqloh"

    Returns: "vadaizha"

  11. "smqri"

    "smqrihwkgp"

    Returns: "smqria"

  12. "ytlvjyz"

    "yzri"

    Returns: "ytlvjyza"

  13. "rsbpjymix"

    "rsbpjzhtd"

    Returns: "rsbpjymixa"

  14. "mpioa"

    "mpiru"

    Returns: "mpioaa"

  15. "chwbmdacjb"

    "cjhtxrers"

    Returns: "chwbmdacjba"

  16. "tscsnlj"

    "tscsypte"

    Returns: "tscsnlja"

  17. "qlzk"

    "qoa"

    Returns: "qlzka"

  18. "dvooiurvwb"

    "dvooiurvwr"

    Returns: "dvooiurvwba"

  19. "mcxzdqwrxz"

    "mcxzdqwsj"

    Returns: "mcxzdqwrxza"

  20. "yvgxuc"

    "yvgxuczjmk"

    Returns: "yvgxuca"

  21. "ldctxnlb"

    "ldctxnlbg"

    Returns: "ldctxnlba"

  22. "vjoyokv"

    "vjoyokvs"

    Returns: "vjoyokva"

  23. "aanoqotkpn"

    "aanoqotq"

    Returns: "aanoqotkpna"

  24. "qikratvmt"

    "qikratvmtf"

    Returns: "qikratvmta"

  25. "matexcrmap"

    "matexcrmau"

    Returns: "matexcrmapa"

  26. "xdqmd"

    "xdqmdnrd"

    Returns: "xdqmda"

  27. "fvppotcmq"

    "fvppotcmqk"

    Returns: "fvppotcmqa"

  28. "i"

    "imthurlzzd"

    Returns: "ia"

  29. "cfsdhc"

    "cfsdhq"

    Returns: "cfsdhca"

  30. "xfc"

    "xfsm"

    Returns: "xfca"

  31. "dnjruv"

    "dnjruyc"

    Returns: "dnjruva"

  32. "dbgzrlzqqn"

    "dbgzronvnx"

    Returns: "dbgzrlzqqna"

  33. "agkbtndpxq"

    "agkbtndwqd"

    Returns: "agkbtndpxqa"

  34. "gua"

    "guatvjn"

    Returns: "guaa"

  35. "nlypibx"

    "nxwphimbam"

    Returns: "nlypibxa"

  36. "ynll"

    "ynloccpi"

    Returns: "ynlla"

  37. "fhnp"

    "fjad"

    Returns: "fhnpa"

  38. "sairgrlpg"

    "sairgrlpgv"

    Returns: "sairgrlpga"

  39. "qlbcjtbt"

    "qlbcjtonx"

    Returns: "qlbcjtbta"

  40. "xcinl"

    "xcinlmmfja"

    Returns: "xcinla"

  41. "ey"

    "ruoiuu"

    Returns: "eya"

  42. "cbdq"

    "cbtj"

    Returns: "cbdqa"

  43. "tnrxptsaft"

    "tnrxptsafz"

    Returns: "tnrxptsafta"

  44. "otjnyota"

    "otjnyotzzp"

    Returns: "otjnyotaa"

  45. "xnklrjzj"

    "xnklrjzo"

    Returns: "xnklrjzja"

  46. "keqldefs"

    "keqldefssz"

    Returns: "keqldefsa"

  47. "ykuzurgzhb"

    "ykuzurgzm"

    Returns: "ykuzurgzhba"

  48. "ptkrrcide"

    "ptxsvgitmd"

    Returns: "ptkrrcidea"

  49. "rldmtv"

    "rldmuksby"

    Returns: "rldmtva"

  50. "gjoykydes"

    "gjoykydesk"

    Returns: "gjoykydesa"

  51. "djgbituggv"

    "djgbpcm"

    Returns: "djgbituggva"

  52. "ogydu"

    "r"

    Returns: "ogydua"

  53. "yswpzb"

    "yswpzjz"

    Returns: "yswpzba"

  54. "iysbcihtvw"

    "iysbcisu"

    Returns: "iysbcihtvwa"

  55. "sfgsturk"

    "sfgxy"

    Returns: "sfgsturka"

  56. "lffvxcbm"

    "lffvxwoj"

    Returns: "lffvxcbma"

  57. "dzuwpzuikc"

    "dzuwpzuikt"

    Returns: "dzuwpzuikca"

  58. "kojfhfir"

    "kojfhfyqh"

    Returns: "kojfhfira"

  59. "obcxexmo"

    "obcxexmoa"

    Returns: "IMPOSSIBLE"

  60. "hbm"

    "hbma"

    Returns: "IMPOSSIBLE"

  61. "rqdraror"

    "rqdrarora"

    Returns: "IMPOSSIBLE"

  62. "sffzyhiv"

    "sffzyhiva"

    Returns: "IMPOSSIBLE"

  63. "grvpqz"

    "grvpqza"

    Returns: "IMPOSSIBLE"

  64. "oikqd"

    "oikqda"

    Returns: "IMPOSSIBLE"

  65. "yizh"

    "yizha"

    Returns: "IMPOSSIBLE"

  66. "z"

    "za"

    Returns: "IMPOSSIBLE"

  67. "hwx"

    "hwxa"

    Returns: "IMPOSSIBLE"

  68. "xwyckxrx"

    "xwyckxrxa"

    Returns: "IMPOSSIBLE"

  69. "kudz"

    "kudza"

    Returns: "IMPOSSIBLE"

  70. "qfile"

    "qfilea"

    Returns: "IMPOSSIBLE"

  71. "cfb"

    "cfba"

    Returns: "IMPOSSIBLE"

  72. "ftuzrttdj"

    "ftuzrttdja"

    Returns: "IMPOSSIBLE"

  73. "z"

    "za"

    Returns: "IMPOSSIBLE"

  74. "fcoidj"

    "fcoidja"

    Returns: "IMPOSSIBLE"

  75. "syyp"

    "syypa"

    Returns: "IMPOSSIBLE"

  76. "yeh"

    "yeha"

    Returns: "IMPOSSIBLE"

  77. "htjivxoza"

    "htjivxozaa"

    Returns: "IMPOSSIBLE"

  78. "gxanf"

    "gxanfa"

    Returns: "IMPOSSIBLE"

  79. "aazz"

    "abaa"

    Returns: "aazza"

  80. "ab"

    "abad"

    Returns: "aba"

  81. "a"

    "za"

    Returns: "aa"

  82. "abc"

    "abcaaa"

    Returns: "abca"

  83. "aaa"

    "aaaaaa"

    Returns: "aaaa"

  84. "aaa"

    "aaaaa"

    Returns: "aaaa"

  85. "aaaa"

    "zzzza"

    Returns: "aaaaa"

  86. "aba"

    "abca"

    Returns: "abaa"

  87. "abc"

    "abca"

    Returns: "IMPOSSIBLE"

  88. "aba"

    "abac"

    Returns: "abaa"

  89. "aa"

    "aaaaa"

    Returns: "aaa"

  90. "abc"

    "abcd"

    Returns: "abca"

  91. "b"

    "baa"

    Returns: "ba"

  92. "azzzzzzzzz"

    "b"

    Returns: "azzzzzzzzza"

  93. "aa"

    "aaab"

    Returns: "aaa"

  94. "car"

    "hacar"

    Returns: "cara"

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: