Statistics

Problem Statement for "STable"

Problem Statement

You are given two Strings s and t. All characters of s and t are distinct. No character of s is present in t and no character of t is present in s.

Let N be the length of s, and M be the length of t. Define a 2-dimensional string array "table" as follows:

  • table[i][0] = s[i-1] (1<=i<=N)
  • table[0][j] = t[j-1] (1<=j<=M)
  • table[i][j] = min(table[i-1][j], table[i][j-1]) + max(table[i-1][j], table[i][j-1]) (1<=i<=N, 1<=j<=M)

Note that min and max are defined by the lexicographical order of strings (see Notes for a more formal definition), and A+B means the concatenation of strings A and B.

Your task is to find a substring of table[N][M]. Let L be the length of table[N][M]. Return the substring of table[N][M] whose start position (0-indexed) is pos and length is min(50, L-pos).

Definition

Class:
STable
Method:
getString
Parameters:
String, String, long
Returns:
String
Method signature:
String getString(String s, String t, long pos)
(be sure your method is public)

Notes

  • A string X is defined as smaller than a string Y if and only if X is a prefix of Y or X has a smaller character than Y at the first position where they differ.
  • The order of characters is defined by their ASCII codes: '0'<...<'9'<'A'<...<'Z'<'a'<...<'z'.

Constraints

  • s and t will each contain between 1 and 30 characters, inclusive.
  • All characters of s and t will be distinct.
  • No character of s will be present in t.
  • No character of t will be present in s.
  • s and t will contain only letters ('A'-'Z', 'a'-'z') and digits ('0'-'9').
  • pos will be between 0 and L-1, inclusive, where L is the length of table[N][M] as defined in the statement.

Examples

  1. "ad"

    "cb"

    0

    Returns: "acbacd"

    In this case, the array "table" is as follows. ----------------- | | c | b | ----------------- |a| ac | acb | ----------------- |d| acd |acbacd| -----------------

  2. "fox"

    "cat"

    0

    Returns: "acfcfoacftacfcfocfox"

  3. "Ra6b1t"

    "W0lf"

    66

    Returns: "RWab0RWRWa0RWl0RWRWa6RWa0RWRWa6RWa6RWab0RWRWa6RWa6"

    In this case, return 50 characters.

  4. "M0HAXG"

    "COFU12"

    919

    Returns: "MOFU2"

  5. "a0B1c2D3e4F5gHiJkLmN"

    "A9b8C7d6EfGhIjKlMn"

    9876543210

    Returns: "B10AaB1c0Aa9Aa0AaB0AaB10AaB1c0AaB1c20Aa9Aa0AaB0Aa9"

  6. "TCOR2"

    "MEDiUm"

    350

    Returns: "MTDEMTiCMTEMTDEMTDEMTiDEMTiUCMTEMTCMTOCMTEMTDEMTCM"

  7. "A"

    "B"

    0

    Returns: "AB"

  8. "B"

    "A"

    0

    Returns: "AB"

  9. "F1"

    "7"

    0

    Returns: "17F"

  10. "KwC"

    "I"

    0

    Returns: "CIKw"

  11. "db"

    "RU"

    0

    Returns: "RdURdb"

  12. "bi"

    "0O"

    2

    Returns: "O0bi"

  13. "O"

    "Be"

    1

    Returns: "Oe"

  14. "q"

    "mKo"

    2

    Returns: "qo"

  15. "6"

    "Giu1"

    1

    Returns: "6Giu"

  16. "jR8bez7Nn"

    "LvcYOo"

    2764

    Returns: "RLjvLjRLjvLjvc8LjRLjRLjv8LjRb8LjRbe8LjRLjRLjv8LjRb"

  17. "5F0IQGf9"

    "Ug4YljH3hwsL"

    77285

    Returns: "45UgYl45UgYlj05UF5UF5Ug05UFI05UF5UF5Ug45Ug5UF5Ug05"

  18. "xSaGFXp"

    "yZ0vQtPICgTRVhwnjc"

    445506

    Returns: "SxyZxy0Zxyv0ZxyvQ0ZxyvQt0ZxyvQtP0ZxyvQtPI0ZxyvQtPI"

  19. "wHqtdj"

    "fpVaMoi9rXJEQ1xsu8yPeIl4"

    74140

    Returns: "fwfwpVfwpVfwpaMVfwpaMVfwpaoMVfwpaoi9MVfwpaoir9MVfw"

  20. "PgDj1"

    "d7z9sO04L6XGvJkNqQfIlV8ECpc5Ty"

    65678

    Returns: "kN07Pdz9sO4L6XGvJkNq07Pdz9sO4L6XGvJkNqQ07Pdz9sO4L6"

  21. "y4zUXI"

    "iCkM"

    151

    Returns: "y4iyz4iyzU4iyCiy4iyz4iyzU4iyzUX4iyCiy4iyz4iyzU4iyz"

  22. "yS7mWPNJoQbF"

    "p5T8g"

    2737

    Returns: "5pySpy7Spy7Spym5pySpy7Spy7Spym7SpymW5pySpy7Spy7Spy"

  23. "NY72ZOCDnMo8XzVElB"

    "ePgu4h"

    35692

    Returns: "OCDnMo8X27NeY7NeYNePNeY27NeYZ27NeY7NeYNePNeY7NeYNe"

  24. "cCtNi5mhGLsr6lvXgVwYWzn7"

    "xeq3f4F"

    830382

    Returns: "iCcxcxeCcxtCcxtNCcxtNi5CcxtNim5CcxtNimh5CcxtNimhG5"

  25. "saqH5ZGYIluhj6y3nkfUWE4SgARV1Q"

    "oiL897pw"

    2161122

    Returns: "osiosaosq5HaosqZ5HaosqZG5HaosqZGY5HaosqZGYI5HaosqZ"

  26. "7RNr04OhYmX5CJwExsipuIq6MBTt3e"

    "P"

    0

    Returns: "07PRNr4OhYmX5CJwExsipuIq6MBTt3e"

  27. "duCpMfUEawZ4AqJc8Q5PVr0v3bo1Yh"

    "7k"

    0

    Returns: "047duCpMfUEawZAqJc8Q5PVr47duCpMfUEawZ7dk7du7duC7du"

  28. "l"

    "cwPC8fRFSbTrYjOIeMm9s0Zd2WgHhJ"

    0

    Returns: "08CPclwfRFSbTrYjOIeMm9sZd2WgHhJ"

  29. "d6jpx9WGrtCZc4mbMRF3hYyVTDUfH0"

    "8uzEsXBJeS1PgQkLO27Kin5wINaoAq"

    105675228333950900

    Returns: "sXBJ8duzEsXBJe68d8du8duz8duzE8duzEs8duzEsX8duzEsXB"

  30. "4DJO7URxCftKMYkg8Wlzj6reIqXd1G"

    "ucpVNs2FP9EmAHy3vbZw0aSoQnTBLi"

    116778480903908552

    Returns: "c4ucp4ucpV4ucpVN4ucpVNs4uD4uc4uDJ4uD4uc4ucp4uD4uc4"

  31. "m6pjSU2tcK0BeoIVADZwGqrkXaEliP"

    "b8uFvhgL4yROH9d3CfQsJT5zx7YM1N"

    94540111814366875

    Returns: "m8bm8bmu6bm8bm8bmu8bmuF6bm8bm6bmp6bm8bm8bmu6bm8bm8"

  32. "pa1TY9oOnjfvwFulVIbhAGyd6mkNgZ"

    "BrL3KzR8MJc7q2WDxsHCiUP0etE4SX"

    43462944365656915

    Returns: "prL3BprLK3BprLKz1BpaBpaBprBpaBprBprL3BprLBpaBprBpr"

  33. "FXSaEZrBTVminNKMkJuwQIoc9qDO6l"

    "YHp1sW7bx4U2yghvftL3zPjAGC08Re"

    12331764517653315

    Returns: "SaFYHFYXFYHpFYHFYXFYXSFYHFYXFYXSFYXSaEFYXSaFYHFYXF"

  34. "oIDNafw58pectC9kYmdlOGMTsKiSxV"

    "u0L4RbrUzq3BQhZH1WPgEj6FvX72An"

    72035084636422803

    Returns: "uL40ouL4R0ouL4Rb0ouIou0ouL0ouL40ouL4R0ouL4Rb0ouL4R"

  35. "WGAwYcQsTUbqzSBJ9nFjihalgCrPZN"

    "8m6K5kfRv4LMuI1X2OHxdVe0tEpD37"

    32656470956804527

    Returns: "AwYcQs68Wm8WG8Wm68WmK68Wm8WG8Wm8WG8Wm8WGA68Wm8WG8W"

  36. "tp4n6RSy0QqcbVgBX2PzJKGoxleUWL"

    "hk1uaHs79jYfiIMTCA8mr5ENdwZDvO"

    62105656205686280

    Returns: "Sy1htkhtkhtp4htphtkhtp4htphtkhtp4htpn4htphtkhtp4ht"

  37. "z2pN1Ec6nPvgB3FZhrX0tjQ9CVTAUd"

    "YyJaHolLKwmb5IR4k7qeiOsuWMfSGx"

    116961845452849671

    Returns: "YzyaolL2YzYzy2Yzp2YzYzyJYzy2YzYzy2Yzp2YzpN2YzYzy2Y"

  38. "JO8jQo0uK9kTZGghSXzl7vqysd3L2N"

    "HFcIpbErfPm4iBaDx61UMC5twARWYV"

    102357438402340721

    Returns: "HJOj8HJOjQ8HJOjQo08HJOjQo8HJOFHJHJO8HJOj8HJOjQ8HJO"

  39. "sbNraVCAtzK25hFX7jYgmxLRkHiDwE"

    "W8TPZ0IqS3eOdcy9oMvu1JlfBp4QGU"

    0

    Returns: "08WsTPZ8WsT8WsWsb8WsTP8WsTPZ08WsTPZI08WsTPZ8WsT8Ws"

  40. "ErGTN6FfRUsCuq5wogdYSa0nKB43PI"

    "tW8AMkZlDHhxbei12z7vVypcXjOLmQ"

    0

    Returns: "056EtrGTNFfRUsCuqwogdYSa56EtrGTNFfRUsCuq6EtrGTNEtW"

  41. "recGhdlKOy9qbPVY38AL0Rkw6a25SN"

    "Mpzx1nFQsfmiETXW7JItuBgjUo4ZC"

    1

    Returns: "39GMrechdlKOyqbPVY8AL39GMrechdlKOyqbPVY839GMrechdl"

  42. "L8dp56WjCOireFDhomvz1YMxXPSRHN"

    "2c0guU3Vs7wtT9nGBkaZybqJfKlA4"

    2

    Returns: "Lc2L82Lc02Lcg02Lc2L82Lc2L82Lc2L8d02Lc2L82Lc02Lcg02"

  43. "EY61QNW78pnZGO5RcJXhivMeqlrIS4"

    "DBzyb2ATmagjftw9PsokxHLuFd03UK"

    118264581564861375

    Returns: "ZGO5RcJXhivMeqlrIS16DEYQNW78pnZGO5RcJXhivMeqlrIS4"

  44. "oxkzCd6mGf5AQqUuihYOVPnK9FWyXM"

    "bcpJ2N7TvEB8Dl1gtjLSseZH03rR4w"

    118264581564861376

    Returns: "QqUuihYOVPnK9FWyX56CboxkzdmGfAQqUuihYOVPnK9FWyXM"

  45. "hYQUm7yakRKHjqE0LWFPvN2JwcrsCS"

    "5fTgAdG3op6Me9VX8biIlDuzOn1xZ4"

    118264581564861423

    Returns: "n"

  46. "9dKW7s6zJ1cGU4HaTvqwZXAYIr2Roe"

    "V8LfPBknMlj50ObmtSui3xyNgCFphD"

    118264581564861422

    Returns: "oe"

  47. "Jb0sI5BUq1juYeL6FvZ4ktMGgwynC"

    "2SD3Nd7Qo8HirlTmKOpXRVhfPczxAW"

    59132290782430711

    Returns: "W"

  48. "QCh0NSfKtHexBojVqzgTDvZFuU4Gb"

    "lYLXP5ndi6ay9Ewr8J1MIR7m3WkOsA"

    59132290782430710

    Returns: "sA"

  49. "SX4gxuwW7r3Q5aqPUTd2zo81LiYGE"

    "HkOcAMeJCvIfnlZKtDp0F6b9hmyRVN"

    59132290782430664

    Returns: "CvIfnlZKtAHSkOcMeJCvIfnlZKtDAHSkOcMeJCvIfnlZKtDp"

  50. "SgLPDA6v4MepcHi9KCn8TdNlbE7tYI"

    "JZRXmGBqWosVQ1xOzUjy32uw0fk5"

    29065024282889623

    Returns: "pcHi9KCn8TdNlbE7tY46ADJSgLPvMepcHi9KCn8TdNlbE7tYI"

  51. "0123456789ABCDEFGHIJKLMNOPQRST"

    "UVWXYZabcdefghijklmnopqrstuvwx"

    98002241560775696

    Returns: "0U10UV0UVW0UVWX0U10UV0UVW0UVWX0UVWXY0U10UV0U120U10"

  52. "0123456789ABCDEFGHIJKLMNOPQRST"

    "UVWXY"

    139479

    Returns: "U1234560U12345670U123456780U1234567890U10UV0U120U1"

  53. "012"

    "3456789ABCDEFGHIJKLMNOPQRSTUVW"

    4739

    Returns: "FGHIJKLMN03456789ABCDEFGHIJKLMNO03456789ABCDEFGHIJ"

  54. "0123456789ABCDEFGHIJKLMNOPQRST"

    "xwvutsrqponmlkjihgfedcbaZYXWVU"

    59079096593332228

    Returns: "x10xw0x120x10xw0xwv0x10xw0x120x1230x10xw0x120x1230"

  55. "0123456789ABCDEFGHIJKLMNOPQRST"

    "YXWVU"

    239785

    Returns: "230Y12340Y123450Y10YX0Y120Y1230Y12340Y123450Y12345"

  56. "012"

    "WVUTSRQPONMLKJIHGFEDCBA9876543"

    5443

    Returns: "FEDCBA9876543"

  57. "TSRQPONMLKJIHGFEDCBA9876543210"

    "UVWXYZabcdefghijklmnopqrstuvwx"

    14445064914415568

    Returns: "WXYZTUVWXYZaOPQRSTUPQRSTUQRSTURSTUSTUTUVPQRSTUQRST"

  58. "TSRQPONMLKJIHGFEDCBA9876543210"

    "UVWXY"

    218099

    Returns: "TUGHIJKLMNOPQRSTUHIJKLMNOPQRSTUIJKLMNOPQRSTUJKLMNO"

  59. "210"

    "3456789ABCDEFGHIJKLMNOPQRSTUVW"

    5161

    Returns: "DEFGHIJKL23456789ABCDEFGHIJKLM23456789ABCDEFGHIJKL"

  60. "TSRQPONMLKJIHGFEDCBA9876543210"

    "xwvutsrqponmlkjihgfedcbaZYXWVU"

    104146795600956101

    Returns: "QRSTxRSTxSTxTxwRSTxSTxTxwSTxTxwTxwvQRSTxRSTxSTxTxw"

  61. "TSRQPONMLKJIHGFEDCBA9876543210"

    "YXWVU"

    114302

    Returns: "QRSTYRSTYSTYTYXOPQRSTYPQRSTYQRSTYRSTYSTYTYXPQRSTYQ"

  62. "02468ACEGIKMOQSUWYacegikmoqsuw"

    "13579BDFHJLNPRTVXZbdfhjlnprtvx"

    321

    Returns: "70120130124012013013501201301240124601201301240124"

  63. "02468ACEGIKMOQSUWYacegikmoqsuw"

    "13579BDFHJLNPRTVXZbdfhjlnprtvx"

    118264581564861333

    Returns: "r013579BDFHJLNPRTVXZbdfhjlnprt013579BDFHJLNPRTVXZb"

  64. "02468ACEGIKMOQSUWYacegikmoqsuw"

    "13579BDFHJLNPRTVXZbdfhjlnprtvx"

    50000000000000000

    Returns: "12013013501201301350135701201301350135701357901201"

  65. "z2468AC1GIKMOQSUWYacegikmoqsuw"

    "y3579BDFHJLNPRTVXZb0fhjlnprtvx"

    5000000000000000

    Returns: "z53yz573yz5793yz579B3yz579BD3yz579BDF12yz468AC2yz3"

  66. "wusqomkigecaYWUSQOMKIGECA86420"

    "xvtrpnljhfdbZXVTRPNLJHFDB97531"

    61

    Returns: "468ACEGIKMOQSUWYacegikmoqsuwx68ACEGIKMOQSUWYacegik"

  67. "xvtrpnljhfdbZXVTRPNLJHFDB97531"

    "wusqomkigecaYWUSQOMKIGECA86420"

    118264581564861322

    Returns: "wxtvwxuwxvwxsuwxuwxvwxtvwxuwxvwxqsuwxsuwxuwxvwxsuw"

  68. "wusqomkigecaYWUSQOMKIGECA86420"

    "xvtrpnljhfdbZXVTRPNLJHFDB97531"

    5010000000

    Returns: "moqsuwxmoqsuwxoqsuwxqsuwxsuwxuwxvwxmoqsuwxoqsuwxqs"

  69. "QHvf29o60usgwblm5E7xyjeRc"

    "iB4Pd3tWOGFTLhq"

    2576692

    Returns: "iHQiHQivHQivf4BQiBQiHQiBQiHQiHQivBQiHQiHQivHQivf2H"

  70. "1YwjCI46BmLV89bJ0SOlv5cKaP"

    "kz3RigqdFTpseU7rAxEZynMDQuXf"

    331402368365391

    Returns: "1kz31kY1kz1kYw1kYwj1kY1kz1kYw1kY1kz1kz31kY1kz1kz31"

  71. "1y6lCQ3d75YGFDfMTc2VhU"

    "8jmEIKoOAsiaRbxWS"

    862614

    Returns: "j18y18jm18j18y18y618j18y18y618y6l18j18y18y618y6l18"

  72. "Kh6uD02ywAVPd9ZXMfg"

    "l3SavHpFejbmqRGoi8Jc"

    20196

    Returns: "KlS3KlKlh6Klh3KlKlh6Klh6Klhu3KlKlh3KlS3KlKlh6Klh3K"

  73. "fI3lxiecw7rzXWjudvJVEAoCt9"

    "G0BphmKayL1Z82nY"

    4310465

    Returns: "0GfBp0GfB0GfGfI0GfGfI3GfI0GfB0GfGfI0GfGfI3GfI0GfGf"

  74. "Ey3"

    "0or"

    8

    Returns: "or0Eo0Ey0Ey3"

  75. "VmBPqNiMHQGxcXEbwrkn"

    "AJyZYgvUoOh"

    1069351

    Returns: "PAVJAVmAVmBAVmBPAVmBPqAVJAVmAVmBAVmBPAVmBPqAVmBPqN"

  76. "aAbBcC6dDe5EfFgGhHiIjJkKlLmM"

    "0O1S2P34oQXZpqrUst7uvx98wyY"

    38243453003802

    Returns: "0aAb0aAbB0aA0aO0aAb0aAbB0aAbBc0aA0aO0aAb0aA0aO0aO1"

  77. "qwertyuiopasdfghjklzxcvbnm0123"

    "QWERTYUIOPASDFGHJKLZXCVBNM9876"

    3000000000

    Returns: "wQqweQqwerQqwertQqwertyQqwertyuEQqWQqWQqwQqWQqwQqw"

  78. "QWER1T2Y3U4IOPASDFGHJKLZXCVBNM"

    "zxcvbnmas5dfg6hjkl7qwe8rtyuiop"

    77558735

    Returns: "WQzWQzxQzWQzxQzxc1EQzWREQzWQzWQzxEQzWR1EQzWRT1EQzW"

  79. "ACEGIKMOQSUWYacegikmoqsuwy0246"

    "BDFHJLNPRTVXZbdfhjlnprtvxz1357"

    1503363324977052

    Returns: "IKMOQSABCEGIKMOQSUABCABDABCEABCEGABCEGIABCEGIKABCE"

  80. "da"

    "bc"

    0

    Returns: "abdbdc"

  81. "aR0BZ1cs2D3euzX4F5tgUHiJkLQmN"

    "AOx9b8CYVT7d6yEfvWGhqIjKlPMnS"

    9371717418577131

    Returns: "9AaOxbC0AaRAaOAaR0AaRB0AaRAaOAaRAaOAaRAaOx0AaRAaOA"

  82. "koM0KUNO1zB6CFiuA34R7WpQ8gawSh"

    "x2D9bsjHfrJnlE5yIYdZTtGXLvPVem"

    8589934592

    Returns: "kxD2kxkxo2kxD92kxD9b2kxD9bs2kxD2kxkxo2kxD92kxD2kxk"

  83. "XaceYgikmoqsu9wz"

    "bd0fhjlnpWrtQvxUy"

    123456

    Returns: "ace0XbdXbaXbd0Xbdf0XbdXbaXbdXbaXbdXbac0XbdXbaXbdXb"

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: