Statistics

Problem Statement for "NextHomogeneousStrings"

Problem Statement

A string is homogeneous if every contiguous substring of length n contains at most d different characters. For a String seed and a long k, the k-th homogeneous string is defined as the k-th element (0-indexed) in the list of all homogeneous strings which have the same length as seed and are lexicographically greater than or equal to seed. Only strings containing all lowercase letters ('a'-'z') should be considered. Return the k-th homogeneous string. If there are less than k+1 strings in this list, return "" instead (quotes for clarity).

Definition

Class:
NextHomogeneousStrings
Method:
getNext
Parameters:
int, int, String, long
Returns:
String
Method signature:
String getNext(int d, int n, String seed, long k)
(be sure your method is public)

Notes

  • If A and B are two Strings of the same length, then A comes earlier lexicographically than B if it contains a smaller character at the first position where the Strings differ.

Constraints

  • n will be between 1 and 9, inclusive.
  • d will be between 1 and n, inclusive.
  • k will be between 0 and 1000000000000000000 (10^18), inclusive.
  • seed will contain between 1 and 50 characters, inclusive.
  • seed will contain at least n characters.
  • seed will contain only lowercase letters ('a'-'z').

Examples

  1. 1

    2

    "aaa"

    3

    Returns: "ddd"

    The condition n=2 and d=1 requires no two consecutive characters to be different. The only homogeneous strings in this case would be: "aaa", "bbb", "ccc", "ddd", ... , "zzz". "ddd" is the fourth one.

  2. 2

    3

    "abc"

    0

    Returns: "aca"

  3. 2

    4

    "ttrrzz"

    6

    Returns: "ttsssc"

  4. 9

    9

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1000000000000000000

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaakmluxinkecojo"

  5. 8

    9

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1000000000000000000

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaauialgggesdxfk"

  6. 1

    1

    "a"

    4

    Returns: "e"

  7. 1

    1

    "a"

    1234

    Returns: ""

  8. 8

    9

    "abcdefghiaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    0

    Returns: "abcdefgiaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

  9. 2

    7

    "abcdefg"

    0

    Returns: "acaaaaa"

    No longer a tricky case.

  10. 8

    9

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1

    Returns: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

  11. 1

    1

    "aa"

    50

    Returns: "by"

  12. 4

    6

    "aghteassd"

    5378843636977

    Returns: ""

  13. 4

    6

    "aghteassd"

    5378843636978

    Returns: ""

  14. 4

    6

    "aghteassd"

    48143649267

    Returns: "zzzzzzzzz"

  15. 4

    6

    "aghteassd"

    48143649268

    Returns: ""

  16. 4

    6

    "aghteassd"

    100483

    Returns: "aghuuuzzz"

  17. 4

    6

    "aghteassd"

    100484

    Returns: "aghvaaaaa"

  18. 8

    9

    "abcdefghiaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    987654321987654321

    Returns: "abcdefgiaaaaaaaaaaaaaaaaaaaaaaaaaaaaaubjyalyffnphp"

  19. 2

    9

    "qwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvb"

    987654321987654321

    Returns: "wwwwpwwwwwwwwwwswwwwssswssssssssvvsssssssssssdddds"

  20. 2

    6

    "zjbrdidfznptkyrcwzrmtmaovadjmlasjylrlh"

    161017101982535372

    Returns: ""

  21. 3

    9

    "wbtmljcngiqaqhzjlcjmxdv"

    152671632822947363

    Returns: ""

  22. 3

    9

    "ffsudovdvcmmfazzygxcldfsuhsabaac"

    588618793123736163

    Returns: "ffttnnnnffnnnggggghggqgqggggqvgv"

  23. 1

    4

    "mjiswggoyaqlbtpvuurwwd"

    508076030000877367

    Returns: ""

  24. 1

    2

    "mydkhjjolaqyyuio"

    681796813750870494

    Returns: ""

  25. 7

    7

    "ugpsqhcqahexziucmeokoreohlgqqeax"

    458693086742393099

    Returns: "ugpsqhcqahexziucmeopjqmdoeeiqtyw"

  26. 1

    2

    "layaqtvwggs"

    827363008135085348

    Returns: ""

  27. 1

    1

    "iuwdqufhsngbjazb"

    627734589849298739

    Returns: "iuwkfuytunhkornq"

  28. 1

    6

    "xqrwgfxyytbpwr"

    35860789315137365

    Returns: ""

  29. 3

    5

    "hqcnvbmlc"

    780809284454958633

    Returns: ""

  30. 6

    6

    "pvjttzt"

    15251967175865072

    Returns: ""

  31. 4

    9

    "qljnixcentuhjlledirixxnqhojmcurtnov"

    744705331172606588

    Returns: "qljnjjjjjaaaaaashhooaaaogaagazagfgg"

  32. 1

    8

    "ujesavkyownmaragmeuzavtkmqggqwcirbm"

    224612649071353125

    Returns: ""

  33. 1

    7

    "efsclljepzunaspmnd"

    122628963912712396

    Returns: ""

  34. 6

    9

    "qcidxqymibe"

    999774354670631733

    Returns: ""

  35. 6

    8

    "veizshplcathrtdw"

    565437263355050623

    Returns: "vfeeppclyyftfbyt"

  36. 6

    6

    "rttchyrfojswsypgioatxgpxquksuyjlbgjpvqcpoarstyxijv"

    8303933872856992

    Returns: "rttchyrfojswsypgioatxgpxquksuyjlbgjpvqewjlimcgwpzb"

  37. 1

    1

    "nliktkmwugszkielaxvwotpqvwiwfwwjzogdco"

    820406421532403027

    Returns: "nliktkmwugszkielaxvwotpqweyjvleemqquxl"

  38. 3

    9

    "vuveefytcrjqydefnmvzhamnbpdxreffnlhxgzymbpwenqjz"

    370529795734391525

    Returns: "vuveeueeeeeaaaaaaaaaaxakkxxaxxxaaaxaxttttaattaff"

  39. 4

    7

    "rubryewwnhzafsrvmafsqrugxdmewguibkdm"

    183118399013308547

    Returns: "rubryrbbaaaaaaaaaaazzzqvzqaazzzyoozx"

  40. 2

    2

    "ssadtklkuitxnbyxdepowgdnyfwskituxckavlfmsvzja"

    451492565914815456

    Returns: "ssadtklkuitxnbyxdepowgdnyfwskitvbvkifxornmogs"

  41. 3

    6

    "uffpnxkyxkmzepvciwdvprezvmofabmihbzxfwwyrmpillchl"

    990085593971163469

    Returns: "uffppfaaaaaaaaaaaaaaaaaaaaeggeeooooowbbwbbdbbwwwy"

  42. 1

    2

    "yu"

    191001040783842403

    Returns: ""

  43. 1

    1

    "kfpjhnbcnbbwebhqonctaqscwmrpgfyidkvwvllhimuwchdnh"

    404657974508279689

    Returns: "kfpjhnbcnbbwebhqonctaqscwmrpgfyidkvwzrruulkxhbrsw"

  44. 4

    9

    "yufuclfizyuupzonqrahwbm"

    659777990501168730

    Returns: "yuujjuiiixixxghxhhxuuua"

  45. 1

    2

    "blxwrhexzgdirezewgogvqmikdjxwjxhcfajdzvbxauo"

    285072968968476570

    Returns: ""

  46. 1

    1

    "epdboa"

    811243207234742873

    Returns: ""

  47. 7

    7

    "ufwfbcqakudpfvmbpjekgirnxtnyybxynccextdqyimwfx"

    636965764229081671

    Returns: "ufwfbcqakudpfvmbpjekgirnxtnyybxynittbkckuonaoe"

  48. 2

    5

    "meauha"

    731817502470930227

    Returns: ""

  49. 1

    4

    "wyxajlaohipmhnpeetnumnithfzwlgurgnrjuppu"

    838115371368469190

    Returns: ""

  50. 4

    7

    "qvotybknzswfgqnbzogptcrlryerekxfbjnkebdpnlub"

    840151680346107411

    Returns: "qvouoooaaaaaaaaaaaaaaaaaaammemmbmmqqrrrdrwvw"

  51. 5

    7

    "dmqfxmpgrkmmsqddsrorxxyjwzibgyrtbxrezaqeko"

    638712155222560570

    Returns: "dmqfxmqaaaaaaaaaaaaaaaaaaaajghwggohxooxniz"

  52. 1

    2

    "fmszipy"

    611013320506975062

    Returns: ""

  53. 1

    4

    "nivqoquciasgtwyc"

    632079707877440250

    Returns: ""

  54. 1

    3

    "qireqzuusxvalhqgntsckcccsoecdfntetlyzzwyn"

    880601761534185111

    Returns: ""

  55. 1

    1

    "ejafzafj"

    243741281353272774

    Returns: ""

  56. 2

    7

    "pmxaabwjgodfpntghulbhkrdvwlfauqzqfei"

    986931023339269

    Returns: ""

  57. 9

    9

    "ookatvjoaaevyfisfw"

    638846775380157723

    Returns: "ookaucbpmcqufmodkl"

  58. 1

    1

    "rjymapgu"

    566368663660497470

    Returns: ""

  59. 5

    5

    "qzazimjdrgrslpdaxevbhnbdniruhdqeynvbzwiqisr"

    367830453719327590

    Returns: "qzazimjdrgrslpdaxevbhnbdniruhdubeekwogdknfv"

  60. 1

    1

    "xzsylwfuhgqnnstfkhqutorezzozegeaqmyickfxnbcvkvdw"

    430992096425720848

    Returns: "xzsylwfuhgqnnstfkhqutorezzozegeaqmympvhojukklavo"

  61. 5

    7

    "zimungfe"

    681294360739127187

    Returns: ""

  62. 6

    7

    "ngtdfdxfxwtkuygcqaxvuechsthespfjgglgpdnerup"

    803543297882298575

    Returns: "ngtdfdxfxwtkvffaaaaaaaaaaaaaacpcvpvezhvulvh"

  63. 3

    8

    "uhwvcsnxavqcz"

    874620457882883753

    Returns: ""

  64. 1

    1

    "gicodweaekevdtfrxikgxmltutketygtvd"

    269300565842669697

    Returns: "gicodweaekevdtfrxikgxphdmfxmyymjyo"

  65. 2

    7

    "bfaziwupfhpffwqijbuokoakunmzushjhghxclqtnnqzaie"

    101848840541077234

    Returns: "bjbbjbbbjbbbbbboooooooxoxxxooooooopppppppppppdd"

  66. 2

    2

    "lranmbtmpimvfofcgicezebgnhcysuuvfgupbewgk"

    557502849839491807

    Returns: "lranmbtmpimvfofcgicezebgnhcyyqsbmaprkyrub"

  67. 2

    4

    "rrbuubejbiftlfqvhqddtkcgdzhohcifvbsubglhw"

    611434323312655713

    Returns: "rrcccaaaaaaxxxhhhqqqdddbbbmmmmdmmmtttrrrr"

  68. 3

    3

    "eaogmdhjnfdpijlngqhtcvccvsxgeqfrx"

    222283957814702018

    Returns: "eaogmdhjnfdpijlngqhtfdqswcndnqxil"

  69. 1

    3

    "ronrthhazaadxogpmipwlqpwyueebghejgdqe"

    26297644121207405

    Returns: ""

  70. 6

    8

    "txyaaxaassaaaarghjsdohasdghususdidisisdodo"

    10000000000000000

    Returns: "txyaaxaassaaaarghjsgaaaaaaaaadntffiniqrddy"

  71. 2

    5

    "zzzzzaa"

    100

    Returns: ""

    In this case, there are 25 homogeneous strings that follow the pattern "zzzzzXX", where X is any letter different from 'z'. There are another 25 homogeneous strings that follow the pattern "zzzzzXz". Finally, there are 26 homogeneous strings that begin with "zzzzzz". In total, there are only 25+25+26 = 76 homogeneous strings that are lexicographically greater than or equal to "zzzzzaa".

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: