Statistics

Problem Statement for "ShortPalindromes"

Problem Statement

A palindrome is a String that is spelled the same forward and backwards. Given a String base that may or may not be a palindrome, we can always force base to be a palindrome by adding letters to it. For example, given the word "RACE", we could add the letters "CAR" to its back to get "RACECAR" (quotes for clarity only). However, we are not restricted to adding letters at the back. For example, we could also add the letters "ECA" to the front to get "ECARACE". In fact, we can add letters anywhere in the word, so we could also get "ERCACRE" by adding an 'E' at the beginning, a 'C' after the 'R', and another 'R' before the final 'E'. Your task is to make base into a palindrome by adding as few letters as possible and return the resulting String. When there is more than one palindrome of minimal length that can be made, return the lexicographically earliest (that is, the one that occurs first in alphabetical order).

Definition

Class:
ShortPalindromes
Method:
shortest
Parameters:
String
Returns:
String
Method signature:
String shortest(String base)
(be sure your method is public)

Constraints

  • base contains between 1 and 25 characters, inclusive.
  • Every character in base is an uppercase letter ('A'-'Z').

Examples

  1. "RACE"

    Returns: "ECARACE"

    To make "RACE" into a palindrome, we must add at least three letters. However, there are eight ways to do this by adding exactly three letters: "ECARACE" "ECRARCE" "ERACARE" "ERCACRE" "RACECAR" "RAECEAR" "REACAER" "RECACER" Of these alternatives, "ECARACE" is the lexicographically earliest.

  2. "TOPCODER"

    Returns: "REDTOCPCOTDER"

  3. "Q"

    Returns: "Q"

  4. "MADAMIMADAM"

    Returns: "MADAMIMADAM"

  5. "ALRCAGOEUAOEURGCOEUOOIGFA"

    Returns: "AFLRCAGIOEOUAEOCEGRURGECOEAUOEOIGACRLFA"

  6. "ABCDEFG"

    Returns: "ABCDEFGFEDCBA"

  7. "GFEDCBA"

    Returns: "ABCDEFGFEDCBA"

  8. "AAAAA"

    Returns: "AAAAA"

  9. "AAAAAB"

    Returns: "BAAAAAB"

  10. "ABBBBB"

    Returns: "ABBBBBA"

  11. "GECABDF"

    Returns: "FDBACEGECABDF"

  12. "ACEGFDB"

    Returns: "ABCDEFGFEDCBA"

  13. "ABCDAA"

    Returns: "AABCDCBAA"

  14. "CA"

    Returns: "ACA"

  15. "EDD"

    Returns: "EDDE"

  16. "BEDA"

    Returns: "ABDEDBA"

  17. "BEABB"

    Returns: "BBAEABB"

  18. "DEABCB"

    Returns: "DEABCBAED"

  19. "AECEABA"

    Returns: "ABAECEABA"

  20. "EEDBDEDA"

    Returns: "ADEEDBDEEDA"

  21. "ACBAAADCC"

    Returns: "ACBCDAAADCBCA"

  22. "ACCCCCCBDA"

    Returns: "ADBCCCCCCBDA"

  23. "ACDBABDCCDB"

    Returns: "ABDCCDBABDCCDBA"

  24. "BDDAABCAEAAB"

    Returns: "BADDAEABCBAEADDAB"

  25. "BBCADBCEBBECD"

    Returns: "BBCADBCEBBECBDACBB"

  26. "BCCAADEBCEEBAA"

    Returns: "BCCAADEBCEECBEDAACCB"

  27. "EDCCCECEBACDEBD"

    Returns: "DBEDCABCCECECCBACDEBD"

  28. "CECCDBBBBDBDBCBB"

    Returns: "BBCBECCDBDBBBDBDCCEBCBB"

  29. "BBEDBAEEDEACEDDAC"

    Returns: "BBCADDECDBAEDEDEABDCEDDACBB"

  30. "AEABEDBDBBADEECEDC"

    Returns: "ACDEABCEEDABBDBBADEECBAEDCA"

  31. "AABEDDEBBDBCECDCADD"

    Returns: "AABDEDACDCEBCBDBCBECDCADEDBAA"

  32. "ACCADCCDCDDBBEDACBCB"

    Returns: "ABCBCADCCEBBDCDCDBBECCDACBCBA"

  33. "BEAEDAADADDDDBDDCCABD"

    Returns: "DBEACCEDAADABDDDDBADAADECCAEBD"

  34. "AEEECABCBEAEBBCCACDAEC"

    Returns: "ACEADEECABCCBBEAEBBCCBACEEDAECA"

  35. "AEADACEBABCCBDBAEDCCCBC"

    Returns: "ACBCCCDEABDABCCEBABECCBADBAEDCCCBCA"

  36. "AADEDEBECDCDEBCCECCEACCC"

    Returns: "ACCCADECCDECCBECDCDCEBCCEDCCEDACCCA"

  37. "CBDDECBEDCEBEEEAEBCCAEEAE"

    Returns: "CBDDEACBEDCEACCBEAEEAEBCCAECDEBCAEDDBC"

  38. "HMDCDJKWHWMEDBKWJEKRFHLO"

    Returns: "OLHFMDCDRKEJWKBDEMWHWMEDBKWJEKRDCDMFHLO"

  39. "MWRQIGJTGNKPBHKXQGIIECSF"

    Returns: "FMSCEIWRQIGJQTGNXKHBPBHKXNGTQJGIQRWIECSMF"

  40. "PXVXFOVOXFXUNVKQSVBLTGNL"

    Returns: "LNGPTLBVSQKXVNUXFXOVOXFXUNVXKQSVBLTPGNL"

  41. "QTQDDSEJHKMAVPVVRSITDMMM"

    Returns: "MMMDQTIQDDSEJHKMARVPVPVRAMKHJESDDQITQDMMM"

  42. "UZOUZENQJTNWLRNBTABSNHHZA"

    Returns: "AUZHHOUZENQJSBATBNRLWLRNBTABSJQNEZUOHHZUA"

  43. "EOFYITMBCPSKYNAIBHGVIGFBT"

    Returns: "EOFYITMBCFGPSKYNAIBHGVGHBIANYKSPGFCBMTIYFOE"

  44. "LVJYMTWWFPUAJGFAENQAITSUW"

    Returns: "LVJYMTWWFPUAJGFSTIAENQNEAITSFGJAUPFWWTMYJVL"

  45. "ZNRDGCMXQCSHEIRSONFBOZDFQ"

    Returns: "QFDZOBFNOSRDGIEHSCMQXQMCSHEIGDRSONFBOZDFQ"

  46. "ALRCAGOEUAOERGCOEUOOIGFA"

    Returns: "AFLRCAGIOEOUAEOCEGRGECOEAUOEOIGACRLFA"

  47. "ALRCAGOEUAOEURGCOEUOOIGFA"

    Returns: "AFLRCAGIOEOUAEOCEGRURGECOEAUOEOIGACRLFA"

  48. "ALRCAGOEUAOEXXGCOEUOOIGFA"

    Returns: "AFLRCAGIOEOUAEOCEGXXGECOEAUOEOIGACRLFA"

  49. "ALRCAGOEUAOEXXXCOEUOOIGFA"

    Returns: "AFLRCAGIOEOUAEOCEXXXECOEAUOEOIGACRLFA"

  50. "ABACADAFAGAFAHAJAKABA"

    Returns: "ABACKADJAHAFAGAFAHAJDAKCABA"

  51. "ABACADAEAFAGAHAIAJAKAL"

    Returns: "ABLACKADJAEIAFHAGAHFAIEAJDAKCALBA"

  52. "SDGBIULGIBNEROJOPGERG"

    Returns: "GRESDGPOJORENBIGLULGIBNEROJOPGDSERG"

  53. "TOPCODER"

    Returns: "REDTOCPCOTDER"

  54. "GOOGLE"

    Returns: "ELGOOGLE"

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: