Statistics

Problem Statement for "CommonPalindromicSubsequences"

Problem Statement

A palindrome is a string that is identical to its reverse. For example, "a", "cac", "abba" are all palindromes.

A subsequence of a string S is any string obtained from S by erasing some (possibly all or none) of the letters in S. For example, the strings "", "cb", "abbc" are all subsequences of the string "abcbac", but "cab" and "bbb" are not.

You are given two strings A and B consisting of lowercase English letters. Find the number of distinct non-empty strings S such that S is a subsequence of both A and B and S is a palindrome.

Definition

Class:
CommonPalindromicSubsequences
Method:
count
Parameters:
String, String
Returns:
long
Method signature:
long count(String A, String B)
(be sure your method is public)

Constraints

  • A and B will contain between 1 and 60 characters, inclusive.
  • Each character in A and B will be a lowercase English letter ('a'-'z').

Examples

  1. "abcbac"

    "cacbbda"

    Returns: 10

    There are ten non-empty palindromic subsequences that are common to "abcbac" and "cacbbda". These are: "a", "b", "c", "aa", "bb", "cc", "aba", "aca", "cac", and "abba". Notes: "abcba" is a palindromic subsequence of "abcbac", but it is not a subsequence of "cacbbda", thus it is not counted. "acba" is a common subsequence of both strings, but it is not a palindrome, thus it is not counted either. Even though there are multiple ways to produce the substring "a" from each of the two given strings, it is only counted once.

  2. "a"

    "a"

    Returns: 1

    Smallest possible example. Note that the input strings can be equal.

  3. "bc"

    "adea"

    Returns: 0

    The are no common letters in the strings.

  4. "abcdefghhgfedcba"

    "badcfehgghefcdab"

    Returns: 160

  5. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    Returns: 60

  6. "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"

    "z"

    Returns: 1

  7. "o"

    "oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo"

    Returns: 1

  8. "abababababababababababababababababababababababababababababab"

    "babababababababababababababababababababababababababababababa"

    Returns: 7049152

  9. "babababababababababababababababababababababababababababababa"

    "abbbabbaaabbbababaaabbbaaababaaabbbabbbaabaababaabaaababbbab"

    Returns: 581749

  10. "abbbabbaaabbbababaaabbbaaababaaabbbabbbaabaababaabaaababbbab"

    "abababbbaababbaaaaabbbabbbaaaaaaaababaabbbababbbbbaaaabbbabb"

    Returns: 120905

  11. "abcdefghijklmnopqrstuvwxyzabcddcbazyxwvutsrqponmlkjihgfedcba"

    "abcdefghijklmnopqrstuvwxyzabcddcbazyxwvutsrqponmlkjihgfedcba"

    Returns: 2147483582

  12. "abcdefghijklmnopqrstuvwxyzabcddcbazyxwvutsrqponmlkjihgfedcba"

    "abcdafghitkcmnopqrstuywxyzabcddcbazvxivujsrqponmlkjwhgfedlbe"

    Returns: 2229605

  13. "nandgiobvijxmaymqsbrregqycskhculdupvadhdfbawwczobktpzxeljftc"

    "abcdefghijklmnopqrstuvwxyzabcddcbazyxwvutsrqponmlkjihgfedcba"

    Returns: 1199

  14. "zncdxcdkabxojhdajgbfmqsslpwiiaucmkaezwqpnguvevofdrlttyhyrbbc"

    "nandgiobvijxmaymqsbrregqycskhculdupvadhdfbawwczobktpzxeljftc"

    Returns: 526

  15. "zzzdzzzkzbzzjzdajgbzzzzszzzizazczzaezwqzzgzvzzozdrztzyhyzbzz"

    "zzzzzzzzvzzzzazmzszzrzzqyczkhzzzzzpvzdzdfzzwzzzzzkzpzxezzzzz"

    Returns: 159

  16. "eeeeezeeeeeezeemeeezreeqyeekhezzezpvzdzefezeeezzeeepeeeeeezz"

    "eezeezeeebzzeeeaegeeezesezzizeeceeaeeweeeeeeezoeereteehezeze"

    Returns: 2507

  17. "ueeuuzuuuuuuzuumeuuuueequeeuuuzzuupuzduuuuuueuuzeuupeeuueuzz"

    "uezuuuueeuuuuuuuuuueuueuuzuuzuucueaueueeuuueeuoueuuueuueuuue"

    Returns: 8107

  18. "zzzzuzzzeuzuuzuuzzzeuuzzuzuuzzzzzzzzzzzzuzzezzzzezuzzuzezzue"

    "uzezzzuzuzzzzzzzzzzzzzzqzzeuzuzzuzzuzdzzzuzzeuuzzuzzezzueuzz"

    Returns: 36035

  19. "zzzzuuzzduoqujaxzzzeuuzntzguzzpzzrzzzmzzuzcezwzzvylzzufezzub"

    "uzezzzuzjzuzzzzzzflzyqzvpzzuzuztesznmdodzuzzeruzzuzhezzueuzx"

    Returns: 4359

  20. "rvfmrkacmlyhtsqxtokdcfkxccmybilbbuymccxfcdkotqsutfehymcarmsr"

    "smmrkachmlyftusqxtokdkxccmybilblimkfdotxqstehylmcrmmfvsr"

    Returns: 98303

  21. "smrmkalhmluftusqxtokdkxccmyyicbmimkfdotxqstehylmcrmlfvsr"

    "rvfmrkacmlyhtsqxtokdcfkxccmybilbbuymccxfcdkotqsutfehymcarmsr"

    Returns: 39745

  22. "jighheiicefccdahcbgcedbbfjbbaejjbbebgjfbbdebcchhdcfecfehgij"

    "ihhifcefcdahcbgbedbfjgbbaejjbbjabbgfbeacgchaccfecfiiehgij"

    Returns: 115208

  23. "ihgifcefadahcbhbedbfjgbbaejjbhjcebgfbeacgcbaccfzcfiibhgij"

    "jighheiicefccdahcbgcedbbfjbbaejjbbebgjfbbdebcchhdcfecfehgij"

    Returns: 49393

  24. "abcaacddbccabcbcadcbdadadaaaaaadadadcdacabcbaccbdbdcdaacbba"

    "abbacacdcdbccabcbaadcbdaadaaadadacdacabcbaccbdbdcdcacbb"

    Returns: 1179951

  25. "abbacjcdcdbacabcbbadcbdaadaaabadccdacabcbacc"

    "abcaacddbccabcbcadcbdadadaaaaaadadadcdacabcbaccbdbdcdaacbba"

    Returns: 41418

  26. "babbbbaabbababbaaaaababbaaabbbbaaabbbababbbbabaabababaabaaab"

    "bbabababbbabababaababaaaaabbabaaaabaaaabbaaabbbabaaabaabbbab"

    Returns: 193815

  27. "baabacacababcaacbcccbaccacaabcbaaccbcabccbccbcbbcbabccaacbab"

    "bccbccabcbcbabccaaaacbbbcccbbbaaaacacaacccbcbacccbacacbaabcc"

    Returns: 285783

  28. "caddcaacdcbbbccbaaaccbaaccabcaaaaddcadbdbcbcaddbdadbbacdccaa"

    "caacadbadcdaaadbaccdcbbabdddbaddadbadcacaacbabcaaaacbbcdaccb"

    Returns: 94749

  29. "daeaebebcaeeeedbaaaceedabcedbebeeccbebcddecdddbdddddddaecbde"

    "abdceadddcdcbacbadcebaebaedcadbcecedecddabcdebaeecaceeeeaeda"

    Returns: 72583

  30. "fecfdgcgfaafecdafddfaebgfcbgfaddcfgffbebafgcfacceffcaecggbdc"

    "ggdgdbegcafadccgccgegffgcadaggaeeedffbefgcgceggeagcgeadefaec"

    Returns: 46922

  31. "ajhjjdcedhbccacbhfbhebhbbbhaeaifbggcbjgeiaibaccjhfgegdhjhejb"

    "hagaifdjebfebffejidifccchadegdgddeedjhcfijacehgfhbdddifbaihg"

    Returns: 3844

  32. "ddgamijnddjbilnkkbfmfhfedefjgbfkeliademefhgaedkadakgfbkifcbk"

    "bggdcmefackghagjbajemgkdffljhkfidjlfhniincaeaenccjebnneeealj"

    Returns: 1089

  33. "anodledoghcnhlccbaaefeagdmolbdficlmfbaehhgmhjgbkhiaemhdbecem"

    "mcggnkmgkbfkadjbbkmadefalaiicnmgaknffkmidcdkmmmgobgjfdjidkim"

    Returns: 1149

  34. "kqtmlhrtrgmrbpisepqfgioiinsrpmofafrdmhcbnotobtfrobcmbqmkcctr"

    "onpglekdlmrrtilahqkbkmfljrbdlmagshejmoeptbmsjqkqeajofoggdtjp"

    Returns: 813

  35. "gvjwdvjjafqzzxlcxdzncqgjlapopkvxfgvicetcmkbljopgtqvvhbgsdviv"

    "hesnkqxmwrqidrvmhlubbryktheyentmrobdeyqcrgluaiihveixwjjrqopu"

    Returns: 196

  36. "bb"

    "abbbaaaababababbbba"

    Returns: 2

  37. "aaaaaaaaaaaa"

    "aaaaaaaaaa"

    Returns: 10

  38. "eddcbffbdbcfebabafccbbfbeafcbffdacdafcbddbcbccacabcbcbcaaaa"

    "fffcf"

    Returns: 6

  39. "ccbdfcffbffc"

    "cfece"

    Returns: 4

  40. "aaaaaabbabaaa"

    "bbab"

    Returns: 5

  41. "chgc"

    "bccibaifbaeigbbcgaa"

    Returns: 4

  42. "cqto"

    "eqkhonrtakmm"

    Returns: 3

  43. "c"

    "dbbca"

    Returns: 1

  44. "ae"

    "ebggc"

    Returns: 1

  45. "babab"

    "aabbbbb"

    Returns: 5

  46. "fd"

    "dc"

    Returns: 1

  47. "dcca"

    "acaa"

    Returns: 2

  48. "dcbdccc"

    "bacbcbadaacadbabbaddddcbcbccdbaabdbdabc"

    Returns: 11

  49. "i"

    "bleeppdc"

    Returns: 0

  50. "bafebddeadd"

    "ceaeddeedcfceeceabcfccefebcaaabaebefcceadbafddd"

    Returns: 30

  51. "hjd"

    "ei"

    Returns: 0

  52. "hagibfdfhgbbeheaegfefidacbigc"

    "bch"

    Returns: 3

  53. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    "a"

    Returns: 1

  54. "aaaaaa"

    "aaa"

    Returns: 3

  55. "abcdefghijklmnopqrstuvwxyzzyxaaxyzzyxwvutsrqponmlkjihgfedcba"

    "abcdefghijklmnopqrstuvwxyzzyaxxayzzyxwvutsrqponmlkjihgfedcba"

    Returns: 1090519036

  56. "abcdefghijklmnopqrstuvwxyzabcddcbazyxwvutsrqponmlkjihgfedcba"

    "abcdefghijklmnopqrstuvwxyzabcdcbazyxwvutsrqponmlkjihgfedcba"

    Returns: 1610612690

  57. "abcdefghhgfedcba"

    "zzzzzzzzzzzzzzzzzzzzzbadcfehgghefcdab"

    Returns: 160

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: