Statistics

Problem Statement for "LeftmostDerivation"

Problem Statement

In a Context-Free Grammar, strings are transformed into other strings during a process called a derivation. In our notation, one step of a derivation occurs when an uppercase letter ('A'-'Z') is turned into a string (possibly empty) of uppercase and lowercase letters ('A'-'Z', 'a'-'z'). For example, 
     ZaBcD -> ZagHgcD -> ZagHgcF -> ZaggcF -> Zaggcq
is a derivation transforming ZaBcD into Zaggcq. A derivation is called leftmost if every derivation step replaces the leftmost uppercase letter. Assuming all valid derivation steps are at your disposal, return the leftmost derivation with the smallest number of steps transforming start into finish. Since all possible derivation rules can be used, during each step, choose the leftmost capital letter, and change it to whichever string you want. If there are multiple possible smallest leftmost derivations, return one that comes first lexicographically. Here smallest is measured by the number of steps. To compare two derivations lexicographically, concatenate all of their intermediate strings, and then compare them. As in ASCII, uppercase letters occur lexicographically before lowercase letters. The returned value should be a String[] containing the sequence of intermediate strings, in the order they are created. Element 0 must be start, and the last element must be finish (see the examples for further clarification). If no leftmost derivation is possible, return an empty String[].

Definition

Class:
LeftmostDerivation
Method:
getDeriv
Parameters:
String, String
Returns:
String[]
Method signature:
String[] getDeriv(String start, String finish)
(be sure your method is public)

Constraints

  • start will contain between 1 and 50 characters inclusive.
  • Each character in start will be an uppercase or lowercase letter ('A'-'Z','a'-'z').
  • finish will contain between 1 and 50 characters inclusive.
  • Each character in finish will be an uppercase or lowercase letter ('A'-'Z','a'-'z').
  • start and finish will be distinct.

Examples

  1. "ZaBcD"

    "Zaggcq"

    Returns: { }

    Although a derivation was shown in the problem statement, there is no leftmost derivation that works.

  2. "AH"

    "ABCDEFGH"

    Returns: { "AH", "ABCDEFGH" }

    Here we replace A with ABCDEFG.

  3. "ABC"

    "abc"

    Returns: { "ABC", "BC", "C", "abc" }

    There are numerous leftmost derivations that take 3 steps, so return the one that occurs first lexicographically.

  4. "AaA"

    "aAaa"

    Returns: { "AaA", "aA", "aAaa" }

    Firstly, we delete the leftmost A by replacing it with the empty string. Next we replace the remaining A with Aaa.

  5. "b"

    "c"

    Returns: { }

  6. "ABCDEFGHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX"

    "a"

    Returns: { "ABCDEFGHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "BCDEFGHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "CDEFGHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "DEFGHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "EFGHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "FGHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "GHIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "HIJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "IJMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "JMNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "MNOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "NOPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "OPSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "PSDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "SDQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "DQRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "QRUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "RUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "UVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "VWXYZABCDEFGHIJKLMNOPQRSTUVWX", "WXYZABCDEFGHIJKLMNOPQRSTUVWX", "XYZABCDEFGHIJKLMNOPQRSTUVWX", "YZABCDEFGHIJKLMNOPQRSTUVWX", "ZABCDEFGHIJKLMNOPQRSTUVWX", "ABCDEFGHIJKLMNOPQRSTUVWX", "BCDEFGHIJKLMNOPQRSTUVWX", "CDEFGHIJKLMNOPQRSTUVWX", "DEFGHIJKLMNOPQRSTUVWX", "EFGHIJKLMNOPQRSTUVWX", "FGHIJKLMNOPQRSTUVWX", "GHIJKLMNOPQRSTUVWX", "HIJKLMNOPQRSTUVWX", "IJKLMNOPQRSTUVWX", "JKLMNOPQRSTUVWX", "KLMNOPQRSTUVWX", "LMNOPQRSTUVWX", "MNOPQRSTUVWX", "NOPQRSTUVWX", "OPQRSTUVWX", "PQRSTUVWX", "QRSTUVWX", "RSTUVWX", "STUVWX", "TUVWX", "UVWX", "VWX", "WX", "X", "a" }

  7. "AbAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    Returns: { "AbAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabAA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab" }

  8. "AbAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAc"

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    Returns: { }

  9. "AaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa"

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: { "AaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaaaaaAaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaaaaaaAaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaaaaaaaAaAaAaAaAaAaAaAaAa", "aaaaaaaaaaaaaaaaAaAaAaAaAaAaAaAa", "aaaaaaaaaaaaaaaaaAaAaAaAaAaAaAa", "aaaaaaaaaaaaaaaaaaAaAaAaAaAaAa", "aaaaaaaaaaaaaaaaaaaAaAaAaAaAa", "aaaaaaaaaaaaaaaaaaaaAaAaAaAa", "aaaaaaaaaaaaaaaaaaaaaAaAaAa", "aaaaaaaaaaaaaaaaaaaaaaAaAa", "aaaaaaaaaaaaaaaaaaaaaaaAa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" }

  10. "AaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAaAa"

    "aaaaaaaaaaaaaaaaaaaaaaa"

    Returns: { }

  11. "AaAaAaAa"

    "aaa"

    Returns: { }

  12. "abAba"

    "aba"

    Returns: { }

  13. "abBabBba"

    "abBba"

    Returns: { }

  14. "aa"

    "abba"

    Returns: { }

  15. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA"

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaA", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" }

  16. "XzxcvzxcvzxcvA"

    "XzxcvzxcvzxcvB"

    Returns: { }

  17. "XzxcvzxcvzxcvA"

    "Xzxcvzxcvzxcv"

    Returns: { }

  18. "XzxcvzxcvzxcvA"

    "zxcvzxcvzxcA"

    Returns: { }

  19. "XzxcvzxcvzxcA"

    "zxcvzxcvzxcvA"

    Returns: { "XzxcvzxcvzxcA", "zxcvzxcvzxcA", "zxcvzxcvzxcvA" }

  20. "ABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK"

    "asdfjkljweasdfjkljweasdfjkljweasdfjkljweasdfjkljwe"

    Returns: { "ABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "BCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "CDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "DEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "EGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "GHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "HIJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "IJKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "JKABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "KABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "ABCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "BCDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "CDEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "DEGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "EGHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "GHIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "HIJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "IJKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "JKABCDEGHIJKABCDEGHIJKABCDEGHIJK", "KABCDEGHIJKABCDEGHIJKABCDEGHIJK", "ABCDEGHIJKABCDEGHIJKABCDEGHIJK", "BCDEGHIJKABCDEGHIJKABCDEGHIJK", "CDEGHIJKABCDEGHIJKABCDEGHIJK", "DEGHIJKABCDEGHIJKABCDEGHIJK", "EGHIJKABCDEGHIJKABCDEGHIJK", "GHIJKABCDEGHIJKABCDEGHIJK", "HIJKABCDEGHIJKABCDEGHIJK", "IJKABCDEGHIJKABCDEGHIJK", "JKABCDEGHIJKABCDEGHIJK", "KABCDEGHIJKABCDEGHIJK", "ABCDEGHIJKABCDEGHIJK", "BCDEGHIJKABCDEGHIJK", "CDEGHIJKABCDEGHIJK", "DEGHIJKABCDEGHIJK", "EGHIJKABCDEGHIJK", "GHIJKABCDEGHIJK", "HIJKABCDEGHIJK", "IJKABCDEGHIJK", "JKABCDEGHIJK", "KABCDEGHIJK", "ABCDEGHIJK", "BCDEGHIJK", "CDEGHIJK", "DEGHIJK", "EGHIJK", "GHIJK", "HIJK", "IJK", "JK", "K", "asdfjkljweasdfjkljweasdfjkljweasdfjkljweasdfjkljwe" }

  21. "ABCDEFGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB"

    "abcdefghijklmnopqrstuvwxyzyxwvutsrqponmlkjihgfedcb"

    Returns: { "ABCDEFGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "BCDEFGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "CDEFGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "DEFGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "EFGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "FGHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "GHIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "HIJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "IJKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "JKLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "KLMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "LMNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "MNOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "NOPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "OPQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "PQRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "QRSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "RSTUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "STUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "TUVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "UVWXYZYXWVUTSRQPONMLKJIHGFEDCB", "VWXYZYXWVUTSRQPONMLKJIHGFEDCB", "WXYZYXWVUTSRQPONMLKJIHGFEDCB", "XYZYXWVUTSRQPONMLKJIHGFEDCB", "YZYXWVUTSRQPONMLKJIHGFEDCB", "ZYXWVUTSRQPONMLKJIHGFEDCB", "YXWVUTSRQPONMLKJIHGFEDCB", "XWVUTSRQPONMLKJIHGFEDCB", "WVUTSRQPONMLKJIHGFEDCB", "VUTSRQPONMLKJIHGFEDCB", "UTSRQPONMLKJIHGFEDCB", "TSRQPONMLKJIHGFEDCB", "SRQPONMLKJIHGFEDCB", "RQPONMLKJIHGFEDCB", "QPONMLKJIHGFEDCB", "PONMLKJIHGFEDCB", "ONMLKJIHGFEDCB", "NMLKJIHGFEDCB", "MLKJIHGFEDCB", "LKJIHGFEDCB", "KJIHGFEDCB", "JIHGFEDCB", "IHGFEDCB", "HGFEDCB", "GFEDCB", "FEDCB", "EDCB", "DCB", "CB", "B", "abcdefghijklmnopqrstuvwxyzyxwvutsrqponmlkjihgfedcb" }

  22. "AcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ"

    "aabbctuvecsdfccasdfcfffcccccaccacccacccccabVb"

    Returns: { "AcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffccHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffccccJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccacLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccaccOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccaccRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccaccccTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccabVb" }

  23. "AcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ"

    "aabbctuvecsdfccasdfcfffcccccaccacccaccccVcabb"

    Returns: { }

  24. "AcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ"

    "aabbctuvecsdfccasdfcfffcccccaccacccacccccVabbc"

    Returns: { "AcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbcBcCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecCcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfcDcEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccEcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcFcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcGcHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffccHcIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccIcJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffccccJcKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccKcLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccacLcMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccMcNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacNcOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccaccOcPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccPcQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacQcRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccaccRcScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccScTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccaccccTcUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccUVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccVWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccWXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccXYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccYZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccZ", "aabbctuvecsdfccasdfcfffcccccaccacccacccccVabbc" }

  25. "cTcUVWXYZ"

    "ccVabbc"

    Returns: { "cTcUVWXYZ", "ccUVWXYZ", "ccVWXYZ", "ccWXYZ", "ccXYZ", "ccYZ", "ccZ", "ccVabbc" }

  26. "abcdEabcdEdcba"

    "abcdEdcba"

    Returns: { }

  27. "aAaaaaaaaAa"

    "aaaaaaaaaAa"

    Returns: { "aAaaaaaaaAa", "aaaaaaaaaAa" }

  28. "aaAaaA"

    "aaaaaaaaaaaaA"

    Returns: { "aaAaaA", "aaaaaaaaaaaaA" }

  29. "aaAaaAbA"

    "aaaaaaaaaabA"

    Returns: { "aaAaaAbA", "aaaaAbA", "aaaaaaaaaabA" }

  30. "ABCDEF"

    "ABCDEG"

    Returns: { "ABCDEF", "BCDEF", "CDEF", "DEF", "EF", "F", "ABCDEG" }

  31. "AaBCDEF"

    "AaBCDEG"

    Returns: { }

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: