Statistics

Problem Statement for "OnlySanta"

Problem Statement

Definition: for two strings X and Y, we say that a string X has a subsequence Y if and only if it's possible to remove 0 or more characters in X so that the remaining characters form the string Y. For example, "ABCDEFFF" has subsequences "B", "ABFF" and "ABCDEFFF", but doesn't have subsequences "XSFJ", "BA" and "CCDD".


Kids often want to write a letter to Santa but they make a typo and send them to Satan instead. We say that the address written on an envelope is good if and only if it has the subsequence "SANTA" but it doesn't have the subsequence "SATAN" - otherwise the letter can be sent to the wrong place!


Limak already wrote a string S as the address. It's guaranteed that S doesn't have the subsequence "SATAN", but possibly it doesn't have the subsequence "SANTA" either. Your task is to add some (0 or more) characters anywhere into S, including its beginning and end, so that it is a good address, as defined above.


You are given the String S of length up to 1000 consisting of uppercase English letters, representing the currently written address. Formally, return any string X that satisifes the following conditions:


  1. X has a subsequence S.
  2. X has the subsequence "SANTA".
  3. X doesn't have the subsequence "SATAN".
  4. X has at most 1050 characters.
  5. Each character in X must be an uppercase English letter 'A' - 'Z'.

Definition

Class:
OnlySanta
Method:
solve
Parameters:
String
Returns:
String
Method signature:
String solve(String S)
(be sure your method is public)

Notes

  • It can be proved that a valid answer exists for any valid input.

Constraints

  • S will contain between 1 and 1000 characters, inclusive.
  • Each character in S will be an uppercase English letter: 'A' - 'Z'.
  • S will not have the subsequence "SATAN".

Examples

  1. "STANA"

    Returns: "STANTA"

    Limak already wrote "STANA". He can add a single character 'T' to obtain "STANTA". This string has the subsequence "SANTA" and doesn't have the subsequence "SATAN".

  2. "STN"

    Returns: "SANTNA"

    Here, one correct solution is to add "AN" between 'S' and 'T' and also add 'A' at the end of the string. The returned string is: "S(A)(N)TN(A)", where brackets represent added characters.

  3. "RATSNOOOA"

    Returns: "DEARATSNOOOSANTA"

  4. "SXAYNTA"

    Returns: "OOOOSOXAYNTOOOOAOOO"

    One correct answer is simply "SXAYNTA" because this given string already has the subsequence "SANTA". You don't have to minimize the number of added characters though.

  5. "SNTA"

    Returns: "SANTA"

  6. "ASNTA"

    Returns: "SASNTAS"

  7. "NIELATA"

    Returns: "SANIELATAJA"

  8. "X"

    Returns: "SSAAXNNTTAA"

  9. "ATANSTAN"

    Returns: "ATANSTANTA"

  10. "TNSTNAA"

    Returns: "TNSANTNAATA"

  11. "ABCDEFGHIJK"

    Returns: "ABCDEFGHIJKSANTA"

  12. "ATANATANSTNSTNSTNASNASNTSNSTNSTASTASTA"

    Returns: "ATANATANSTNSTNSTNASNASNTSNSTNSTASTASTATA"

  13. "DONATAN"

    Returns: "DONATANSANTA"

  14. "SANTA"

    Returns: "SANTATA"

  15. "S"

    Returns: "SANTA"

  16. "A"

    Returns: "ASANTA"

  17. "T"

    Returns: "TSANTA"

  18. "N"

    Returns: "NSANTA"

  19. "AA"

    Returns: "AASANTA"

  20. "SAN"

    Returns: "SANTA"

  21. "SATA"

    Returns: "SANATATA"

  22. "STAAN"

    Returns: "STAANTA"

  23. "ATAN"

    Returns: "ATANSANTA"

  24. "SATA"

    Returns: "SANATATA"

  25. "ATANSATA"

    Returns: "ATANSANATATA"

  26. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAASANTA"

  27. "AAABABABABAAABAABABBAAABBBBAABBBBBBBABAAABBAAAAABB"

    Returns: "AAABABABABAAABAABABBAAABBBBAABBBBBBBABAAABBAAAAABBSANTA"

  28. "NZIJDIFYERVJAOALCGXOVLDQFZAORAHDIGYOJKNVIAZTPCMXLV"

    Returns: "NZIJDIFYERVJAOALCGXOVLDQFZAORAHDIGYOJKNVIAZTPCMXLVSANTA"

  29. "TATA"

    Returns: "TATASANTA"

  30. "STANANANTTTTSSSSNNNAA"

    Returns: "STANANANTTTTSSSSNNNAATA"

  31. "SSSTNTNTSAANSNSTTT"

    Returns: "SSSTNTNTSAANSNSTTTTA"

  32. "SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS"

    Returns: "SANSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSTA"

  33. "SANTASATASATASATASATASATASATASATASATASATA"

    Returns: "SANTASATASATASATASATASATASATASATASATASATATA"

  34. "ATNAS"

    Returns: "ATNASANTA"

  35. "NATAS"

    Returns: "NATASANTA"

  36. "ANATS"

    Returns: "ANATSANTA"

  37. "ANANASSSTAANANA"

    Returns: "ANANASSSTAANANATA"

  38. "SONTANA"

    Returns: "SONTANATA"

  39. "ZATAN"

    Returns: "ZATANSANTA"

  40. "ZOLTAN"

    Returns: "ZOLTANSANTA"

  41. "DEVIL"

    Returns: "DEVILSANTA"

  42. "SNAKE"

    Returns: "SANNAKETA"

  43. "SASASASASANNNNNNSASANNTA"

    Returns: "SASASASASANNNNNNSASANNTATA"

  44. "STNTNTASASSAAS"

    Returns: "SANTNTNTASASSAASTA"

  45. "STNTNTASASSAASNTNTNTNT"

    Returns: "STNTNTASASSAASNTNTNTNTTA"

  46. "SNXNNNXNXSNSNXSSXSXXNXXXXSSNXXXSXXXXXXXSNXXXNXXXXS"

    Returns: "SANNXNNNXNXSNSNXSSXSXXNXXXXSSNXXXSXXXXXXXSNXXXNXXXXSTA"

  47. "TAAASTTASTTATATSSATATAATSSASAASSASATATSATASSASAATT"

    Returns: "TAAASANTTASTTATATSSATATAATSSASAASSASATATSATASSASAATTTA"

  48. "TSNTTTTNSTSOOSNOSOSTONSOSNNOOSNTNOSOONNOSSNSTNTNTS"

    Returns: "TSANNTTTTNSTSOOSNOSOSTONSOSNNOOSNTNOSOONNOSSNSTNTNTSTA"

  49. "TATANNAAAATANNTANNATANTTATAAAATANATTAAATNAAATATANN"

    Returns: "TATANNAAAATANNTANNATANTTATAAAATANATTAAATNAAATATANNSANTA"

  50. "MSSTXTASUMAUASMUMTXUSBMXBTAAMUAMATAAMMUXXABUBBMSSA"

    Returns: "MSANSTXTASUMAUASMUMTXUSBMXBTAAMUAMATAAMMUXXABUBBMSSATA"

  51. "SASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASATNAAT"

    Returns: "SASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASASATNAATTA"

  52. "SATN"

    Returns: "SATNTA"

  53. "NANANNNAASATSNSSNSTSSTNT"

    Returns: "NANANNNAASATSNSSNSTSSTNTTA"

  54. "SA"

    Returns: "SANATA"

  55. "TATSSANAANAANTSSNTTSASATATSSAAS"

    Returns: "TATSSANAANAANTSSNTTSASATATSSAASTA"

  56. "SXAYTWN"

    Returns: "SXAYTWNTA"

  57. "SATNN"

    Returns: "SATNNTA"

  58. "TAKNSTGTTHATUHA"

    Returns: "TAKNSANTGTTHATUHATA"

  59. "TN"

    Returns: "TNSANTA"

  60. "SAT"

    Returns: "SANATTA"

  61. "NSATN"

    Returns: "NSATNTA"

  62. "TNSTAST"

    Returns: "TNSANTASTTA"

  63. "SATNTA"

    Returns: "SATNTATA"

  64. "SSATNN"

    Returns: "SSATNNTA"

  65. "ZSZZTSTSTASZZATAATASATTTSAZSSAASASSST"

    Returns: "ZSANZZTSTSTASZZATAATASATTTSAZSSAASASSSTTA"

  66. "ANSAT"

    Returns: "ANSANATTA"

  67. "ATANAN"

    Returns: "ATANANSANTA"

  68. "ANSATA"

    Returns: "ANSANATATA"

  69. "SANAN"

    Returns: "SANANTA"

  70. "NTSAT"

    Returns: "NTSANATTA"

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: