Statistics

Problem Statement for "LongPalindromes"

Problem Statement

There is a string written on a sheet of paper. Katka has an eraser. She would like to erase some (possibly none or all) of the characters in such a way that the remaining letters will form a palindrome. Count the number of ways in which she can do it.

There is a catch: Katka's string is very long.

You are given the int repeats and the String pattern. Katka's string is obtained by concatenating repeats consecutive copies of the string pattern.

Compute and return the number of ways in which Katka can produce a palindrome, modulo 10^9 + 7.

Definition

Class:
LongPalindromes
Method:
count
Parameters:
int, String
Returns:
int
Method signature:
int count(int repeats, String pattern)
(be sure your method is public)

Notes

  • A palindrome is a string that reads the same forwards and backwards. In particular, the empty string is also a palindrome.

Constraints

  • pattern will have between 1 and 50 characters, inclusive.
  • Each character in pattern will be a lowercase English letter ('a'-'z').
  • repeats will be between 1 and 10^9, inclusive.

Examples

  1. 1

    "blob"

    Returns: 8

    The eight valid ways of erasing are the following ones (with periods representing erased letters): .... b... .l.. ..o. ...b b..b bl.b b.ob

  2. 1

    "various"

    Returns: 8

    All the letters are distinct, so Katka must erase all except for at most one.

  3. 30

    "aa"

    Returns: 536396504

    Katka's string consists of 60 occurrences of the letter 'a'. Each of the 2^60 possible ways of erasing some of them produces a palindrome.

  4. 3

    "abac"

    Returns: 343

  5. 987654321

    "qwrtyuqertyuiqeqwertyuqwertzuiqrtyuiopopioqwertyui"

    Returns: 14709905

  6. 1

    "ff"

    Returns: 4

  7. 945353537

    "jbizwnzwoazijeii"

    Returns: 112217208

  8. 354557574

    "pqmfmrhjtjtdmtrdtdhddttdmfjtfbhrjtjtqrhd"

    Returns: 813189368

  9. 802433620

    "tcbfpjvkymkfh"

    Returns: 440808142

  10. 665850735

    "ruapoauuuheaudporfhwlb"

    Returns: 185726497

  11. 62328244

    "ovgzatl"

    Returns: 683246559

  12. 1

    "f"

    Returns: 2

  13. 417526521

    "fibaxroulzlkayqcsfgrdqgucccppcfqdrpnauvnyyogmmc"

    Returns: 963983977

  14. 453793780

    "jzsrtstok"

    Returns: 249311758

  15. 851818544

    "cccpp"

    Returns: 128942750

  16. 119513920

    "pdjkrcjc"

    Returns: 359193575

  17. 632112929

    "dmycvytxwkkludvwcmrccrzyvv"

    Returns: 612583387

  18. 572832781

    "nrqcqeggtmezmqsmyriddxwnjocytmeaujyxnzqdnpktn"

    Returns: 390036027

  19. 391251681

    "kzrxrrqshsarabrlxskklmbamaqzkllqrrkqaaxrb"

    Returns: 667816873

  20. 3

    "ff"

    Returns: 64

  21. 988878483

    "twqlxmwxogfqoumrlbdufmxesykxhhmrxftwgmrfiyoldwtkkf"

    Returns: 931159475

  22. 795951975

    "gyzfmfduuyfdffk"

    Returns: 550603149

  23. 1

    "fgsdrewgregregegdsgbxcew"

    Returns: 1930

  24. 399695763

    "hzssfhrsrzssrfrhzzfhfszzshzrfhzhfr"

    Returns: 534547506

  25. 68148874

    "brx"

    Returns: 984744787

  26. 216363667

    "cbccssbbc"

    Returns: 200494369

  27. 454128578

    "mmyyymmyymyyyymyyymyymymmmmmmm"

    Returns: 578211335

  28. 720412492

    "ow"

    Returns: 561860473

  29. 330453699

    "ocoaytyiexhxkxoh"

    Returns: 795057895

  30. 212982249

    "gkhbwqk"

    Returns: 642189750

  31. 962856227

    "ytyytttyyttyyttyyytyyyyttttytyytyt"

    Returns: 602332479

  32. 2

    "fgsdrewgregregegdsgbxcew"

    Returns: 4625198

  33. 3

    "fg"

    Returns: 27

  34. 820193936

    "edkckepkpmpzmpczd"

    Returns: 863189638

  35. 822699848

    "omcjqsmicyxjkbezjnxrd"

    Returns: 769107301

  36. 396477637

    "zseqese"

    Returns: 532749275

  37. 749538922

    "diqvvjvqmhqqvfddvhqivmqphiddhdmfqqpjjfhhjqidvdmi"

    Returns: 462973542

  38. 2

    "f"

    Returns: 4

  39. 293970757

    "aflauifwagwtsikkstlutjksbsfistluugflfbsiilwtwvlkk"

    Returns: 179427127

  40. 818624438

    "jyxxrrwqwjnrypnrjnwa"

    Returns: 632502862

  41. 207912919

    "cy"

    Returns: 734791817

  42. 980750914

    "tppztj"

    Returns: 462094776

  43. 213253713

    "ywwwwywwywyywywykkykwykywkkyywkykwyywwywwkk"

    Returns: 94330129

  44. 84539947

    "hileexfwmlpfifwpbxfxocxiywmwbfpefgce"

    Returns: 240550293

  45. 214271585

    "onoocaelnmecpansceqqlsemqosnmleae"

    Returns: 390424993

  46. 29553324

    "yrvu"

    Returns: 712707508

  47. 404231801

    "vdzzjjhsfvzhprfvvjzzcfaaesvsfjj"

    Returns: 266283783

  48. 2

    "ff"

    Returns: 16

  49. 631512670

    "asdtadtjyystdiisdjjjdijsaiiisisjjis"

    Returns: 523968550

  50. 267563096

    "pdaaaeodokkasedoksd"

    Returns: 679257679

  51. 492634661

    "xepoxiliolooiixpmieoixpxnnbjxofjxfoloebioofjobpiig"

    Returns: 846800243

  52. 925313470

    "exqtikwgihgcr"

    Returns: 655510298

  53. 993976205

    "hiqjpbbgjphabvwhyqqrpyiijhvwajsasisqisbpwaoabso"

    Returns: 500860376

  54. 40580460

    "iivndiptvflmncvctmufmupi"

    Returns: 584380873

  55. 1

    "fg"

    Returns: 3

  56. 234624604

    "hdgdrobckwkghcogmucquroiowrhyk"

    Returns: 26880911

  57. 702957191

    "nkxcnjlvwcg"

    Returns: 248286495

  58. 813523108

    "zopbpebolcanhkekromws"

    Returns: 274646486

  59. 732818038

    "yqyeyqqiieyqeixxiq"

    Returns: 288844328

  60. 931068192

    "bvbbpfsutkw"

    Returns: 381803866

  61. 215981481

    "iii"

    Returns: 96579415

  62. 68780603

    "ddded"

    Returns: 255958865

  63. 661605766

    "nijzinztnftf"

    Returns: 391884689

  64. 885307932

    "jbbjbbjbbjbbbbjbbjjbjjjbjbbbjbjjjjbbjbbbbjj"

    Returns: 273160699

  65. 740721140

    "wfwijwofngdgffyf"

    Returns: 169948506

  66. 898059518

    "axswysngmvshg"

    Returns: 710841733

  67. 613584398

    "narqbhbaajhrb"

    Returns: 962668623

  68. 288525767

    "ttbqbqybfqbqytftuyyyutytqquufbqyubfy"

    Returns: 904123406

  69. 3

    "f"

    Returns: 8

  70. 712798972

    "ruruurnnurrurru"

    Returns: 683704123

  71. 548947959

    "rzaoaqhgf"

    Returns: 148385469

  72. 847423730

    "xgsgbhflbqbdkgpottzebhdlsqmojiwjytwbmhqw"

    Returns: 132911141

  73. 2

    "fg"

    Returns: 9

  74. 3

    "fgsdrewgregregegdsgbxcew"

    Returns: 186123137

  75. 598922926

    "bcncsqvmckxioommkqocmkvvkxk"

    Returns: 333463236

  76. 1000000000

    "ccbbcbaabcccbabcbcaaaacabbaccccacaabcbbacacaacabcb"

    Returns: 773739877

  77. 23423423

    "aaaaaabbaaaaaaabaaaaabaaaabaaab"

    Returns: 694786151

  78. 12

    "aba"

    Returns: 641125324

  79. 999999999

    "abnowerbnfaeoribfhaeabnowerbnfaeoribfhae"

    Returns: 988230239

  80. 100000000

    "babbbababbaaaaababbaaabbbbaaabbbababbbbabaaba"

    Returns: 861296852

  81. 1000000000

    "asdfasfdsdssadsasaasasassss"

    Returns: 89216380

  82. 1000000000

    "abcbacabbaaabbcabcbcabcbacabbaaabbcabcbcbaccbaabac"

    Returns: 857000438

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: