Statistics

Problem Statement for "PalindromePhrases"

Problem Statement

One of your friends has given you several words and asked you how many palindromic phrases you can compose with those words. To save yourself some time, you've decided to write a program to answer this question. In this problem, a word is defined as a non-empty sequence of lowercase letters ('a'-'z'). A phrase is a non-empty sequence of words, where each pair of consecutive words is separated with exactly one space character. A phrase is palindromic if it reads the same forward and backward, ignoring space characters.

You are given a String[] words. Return the number of different palindromic phrases that can be composed with the given words. Each word in words can be used at most once within each phrase. Two phrases are considered different if they are different strings, even if they read the same when ignoring spaces (for example, "a ba" and "ab a" are different phrases).

Definition

Class:
PalindromePhrases
Method:
getAmount
Parameters:
String[]
Returns:
long
Method signature:
long getAmount(String[] words)
(be sure your method is public)

Constraints

  • words will contain between 1 and 13 elements, inclusive.
  • Each element of words will contain between 1 and 13 lowercase letters ('a'-'z'), inclusive.
  • All elements of words will be distinct.

Examples

  1. {"a","ba"}

    Returns: 2

    You can construct two palindromic phrases "a" and "a ba".

  2. {"ab","bcd","efg"}

    Returns: 0

    No palindromic phrases can be built.

  3. {"a", "bba", "abb"}

    Returns: 7

    Here we have 7 palindromic phrases: "a", "a bba", "abb a", "abb bba", "bba abb", "abb a bba", "bba a abb". Note that even though "a bba" and "abb a" represent the same palindrome, they differ as strings, so we count both of them.

  4. {"aabccc", "ccbbca", "a", "acaabb", "aaa", "aab", "c", "babb", "aacaa", "b"}

    Returns: 47

  5. {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "aaaaaaaaaaaaa"}

    Returns: 16926797485

  6. {"a", "b", "aa", "ab", "ba", "bb", "aaa", "aab", "aba", "abb", "baa", "bab", "bba"}

    Returns: 1081925

  7. {"baabaabbaba", "aaabaa", "b", "ab", "bbbbabbaa", "aabbbab", "bbbbaaa", "aaabaaaa", "bb", "bbba", "aaaaaaab", "bbbb", "abbbbaabaaaaa"}

    Returns: 166

  8. {"bbbb", "bbaaaaaaa", "aabbbababb", "b", "aba", "aaaaba", "babab", "aaabaaaaaaabb", "aabbb", "bbbbbbaa", "aaabaaa", "bb", "abb"}

    Returns: 371

  9. {"aa", "a", "b", "aaabaaaabaab", "bbaababbbbbbb", "bb", "ababaaaaaaa", "ba", "bbb", "bbbbbbbb", "abba", "aaabba", "aaaaaaaababb"}

    Returns: 1353

  10. {"abbbaaa", "bbbbbbbbbb", "ba", "bbb", "bbbb", "aaaaaabbb", "baabbbaaaaa", "aa", "aaaaabaa", "aaa", "bbbbba", "aaabbbbabbb", "bbbbbbbbbbbb"}

    Returns: 1527

  11. {"bbbaaa", "bbb", "abbbbbb", "b", "bbbbbb", "bbbbbbb", "baaaaabbbbb", "aaabbaaaaaaa", "aabbbbbbaaaab", "aaaaaaaaaaa", "aaaaa", "aabbaaabbbbbb", "a"}

    Returns: 2743

  12. {"bbbba", "bbbaaa", "abbb", "baa", "abaaa", "aaaaaaaaa", "aaa", "a", "abbbb", "aaaaabbbbbbb", "bb", "abbbbbbbbbbb", "bbaa"}

    Returns: 3449

  13. {"b", "bbbb", "aaaaaaaaa", "bba", "aa", "aaaaa", "bbbaaa", "aaabaaaab", "bbbbbbbb", "babbbbbbbbbbb", "aaabbbbbb", "a", "bbaaaaaaaaaa"}

    Returns: 6265

  14. {"bbbbb", "bbbba", "abbbbbbbbbb", "aaaab", "bbbbabbbbb", "aaa", "aaaaab", "bbb", "bb", "aaaaa", "aaaaaaaaa", "aaaaaaaaaa", "bbbbbaaa"}

    Returns: 22318

  15. {"aaaab", "bbbbbbbb", "bbbb", "b", "bbbbb", "aaaabb", "aaa", "a", "bbaaaa", "aaabbbaaaaaa", "aa", "aabb", "bbbbbbbbb"}

    Returns: 137781

  16. {"aaaaaaaaa", "aaaa", "b", "aaaaaaaaaaa", "bbb", "aaaaa", "bbaaa", "bbbb", "bb", "bbbbbb", "bbbbbabbbbba", "aa", "bbbbbaaa"}

    Returns: 161460

  17. {"aaaa", "ba", "aaaaaaa", "a", "ab", "bbb", "bbbbbbb", "aabbbbbb", "bbbbaaaabbb", "bbbbb", "b", "aa", "aaa"}

    Returns: 178351

  18. {"bb", "bbbbbbbbbbbb", "a", "bbb", "aaaa", "b", "bbbbbbbb", "bbbbbaaaaa", "bbbbb", "aa", "ba", "aaa", "aaaaaaaaaaaaa"}

    Returns: 568258

  19. {"z","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa"}

    Returns: 1417768545

  20. {"z","az","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa"}

    Returns: 348050484

  21. {"z","aa","aza","aaaa","aazaa","aaaaaa","aaazaaa","aaaaaaaa","aazaaaaaa","aaaaaaaaaa","aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa"}

    Returns: 3391484

  22. {"ddaad", "ca", "daa", "abbbaa", "dd", "aa", "bbb", "ccbbbba", "bbdcccdd", "bbbbccbb", "cccdd", "dccc", "d"}

    Returns: 187

  23. {"abb", "acccb", "dc", "c", "bbbbb", "ccc", "ddc", "a", "d", "cdccc", "dd", "da", "addbabaadaddd"}

    Returns: 660

  24. {"d", "a", "b", "bb", "c", "cb", "ab", "bc", "cbb", "ddcc", "cc", "ccd", "dddc"}

    Returns: 19506

  25. {"abbb", "bb", "a", "b", "ab", "c", "cc", "cca", "ba", "bbb", "ccc", "cbb", "cbc"}

    Returns: 30651

  26. {"bbb", "aaa", "a", "aa", "b", "baa", "bb", "bbbb", "baaa", "aaaa", "ab", "bbaa", "aab"}

    Returns: 1247825

  27. {"aaaaaaaaaaaaa","vvvvvvvvvvvvv","vvvvvvvvvvvv","vv","vvv","vvvv","vvvvv","vvvvvv","vvvvvvv","vvvvvvvv","vvvvvvvvv","vvvvvvvvvv","vvvvvvvvvvv"}

    Returns: 1417768545

  28. {"abcdefghijklm","vvvvvvvvvvvvv","vvvvvvvvvvvv","nopqrstuvwxyz","vvv","vvvv","vvvvv","vvvvvv","vvvvvvv","vvvvvvvv","vvvvvvvvv","vvvvvvvvvv","vvvvvvvvvvv"}

    Returns: 108505111

  29. {"zbmadgjlqetu","b","z","m","g","a","l","j","d","u","q","e","t"}

    Returns: 16

  30. {"g"}

    Returns: 1

  31. {"aaaaaaaaaaaaa","bbbbbbbbbbbbb","ccccccccccccc","ddddddddddddd","eeeeeeeeeeeee","fffffffffffff","ggggggggggggg","hhhhhhhhhhhhh","iiiiiiiiiiiii","jjjjjjjjjjjjj","kkkkkkkkkkkkk","lllllllllllll","mmmmmmmmmmmmm"}

    Returns: 13

  32. {"ofujhrpdlitty","jabdrwtizxfmy","shblupvdfpbay","nuvrylrxphhhd","yttildprhjufo","guljxqbitnlbf","sshyjuazudhta","athduzaujyhss","fblntibqxjlug","yabpfdvpulbhs","ybbfqyfyqfbby","ymfxzitwrdbaj","dhhhpxrlyrvun"}

    Returns: 151945

  33. {"xsomedozrof", "fo", "vdkvmgcrvky", "haiforzodemos", "dvofkgjzudhrq", "wykvrcgmvk", "wdfiqvfzgwaw", "xqrhduzjgk", "pueaqold", "iahaxdloqae", "gzfvqifd", "xa", "up"}

    Returns: 3

  34. {"sqqqp", "lgnrof", "icjplywdjc", "nnztdi", "yyvd", "dvyy", "forngljpqqqs", "dwylpjci", "zqjewjwejqz", "idtznnny", "yn", "cj", "j"}

    Returns: 1370

  35. {"tloluntkgfwo", "lpvitywywy", "owfgktnulolt", "tivplzezgtmiq", "nxqtriomo", "zjxmvuomnyi", "qqpvsvmqdtjw", "qduawfbrxpyc", "wjtdqmvsvpqq", "ylyomoirtqxn", "cypxrbfwaudq", "iynmouvmxjz", "ylyqimtgzez"}

    Returns: 1898

  36. {"lkgiglfjft", "llmqrzsetqgf", "eihlhwhlcsr", "llsjtmgai", "iecpzofybo", "ismiylvqr", "fgqteszrqmll", "yhfykkyfhy", "rsclhwhlh", "ietfjflgigkl", "obyfozpcei", "rqvlyimsi", "iagmtjsll"}

    Returns: 12661

  37. {"aba", "ababa", "abababa", "ababababa", "abababababa", "ababababababa", "b", "bab", "babab", "bababab", "babababab", "bababababab", "babababababab" }

    Returns: 16893295

  38. {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "aaaaaaaaaaaaa" }

    Returns: 16926797485

  39. {"a", "aa", "aaa", "aaba", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "aaaaaaaaaaaaa" }

    Returns: 1416025405

  40. {"a", "ab", "ba", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "aaaaaaaaaaaaa" }

    Returns: 450689647

  41. {"a", "aa", "aba", "aaaa", "aabaa", "aaaaaa", "aaabaaa", "aaaaaaaa", "aaaabaaaa", "aaaaaaaaaa", "aaaaabaaaaa", "aaaaaaaaaaaa", "aaaaaabaaaaaa" }

    Returns: 1803349

  42. {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "aaaaaaaazaaaa" }

    Returns: 1434328329

  43. {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa" }

    Returns: 1302061344

  44. {"aaaaaaaaaaa", "aaa", "aaaaaaaaaa", "aaaaaaaaa", "a", "aaaaaaa", "aaaaaaaa", "aaaaaa", "aaaaa", "aaaaaaaaaaaa", "aaaa", "aa", "aaaaaaaaaaaaa" }

    Returns: 16926797485

  45. {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "bbbbbbbbbbbbb", "aaaaaaaa" }

    Returns: 1434337685

  46. {"b", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "aaaaaaaaaaaaa" }

    Returns: 1417768545

  47. {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaaa", "aaaaaaaaaaaa", "aaaaaaaaaaaaa", "aaaaaa" }

    Returns: 16926797485

  48. {"aaaaaa", "bbbbbb", "cccccc", "dddddd", "eeeeee", "ffffff", "gggggg", "hhhhhh", "bbbbbbaaaaaa", "ddddddcccccc", "ffffffeeeeee", "hhhhhhgggggg" }

    Returns: 1896

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: