Statistics

Problem Statement for "Alignment"

Problem Statement

You are given two Strings: A and B. You would like to align these two strings by inserting '-' characters in them so that every character in A lines up with the same character in B or with a '-' in B, and vice versa. Each maximal sequence of consecutive '-' characters costs x, plus an additional 1 per each '-' character. For example, changing "ABC" to "A-B-C" costs x+1+x+1, while changing it to "A--BC" costs x+2. Given, A, B, and x return the minimum cost to align the two strings.

Definition

Class:
Alignment
Method:
align
Parameters:
String, String, int
Returns:
int
Method signature:
int align(String A, String B, int x)
(be sure your method is public)

Constraints

  • A and B each contain between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
  • x will be between 0 and 100, inclusive.

Examples

  1. "ABC"

    "ACE"

    1

    Returns: 4

    We can line things up as: ABC- A-CE

  2. "AAABAAAABAA"

    "AAAABAABAAA"

    1

    Returns: 7

    AAA-BAAAABAA- AAAABAA--BAAA

  3. "AAABAAAABAA"

    "AAAABAABAAA"

    10

    Returns: 28

    AAABAAAABAA---- AAA----ABAABAAA

  4. "ABCDEFGHJIK"

    "BCDEFGHJIKA"

    0

    Returns: 2

  5. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"

    100

    Returns: 300

  6. "A"

    "B"

    1

    Returns: 4

  7. "AA"

    "B"

    1

    Returns: 5

  8. "VHVIEDVIVMCWTHYCBSOROMRYTZEFL"

    "DDBZZCQPKYPDTRJTCFBAPJYBDDPLKNXHOYHNFVYRORLEIMI"

    3

    Returns: 82

  9. "KBIHFCMBMCIKCJQ"

    "AIJIHGFOPCCPPAOOPKNQCCJNGPIKPFMCIDDFOPLAMDJCLCGF"

    1

    Returns: 55

  10. "PQADAPFMLQVRCCPGTJPVPQVFCJRKO"

    "JGEDTLB"

    2

    Returns: 40

  11. "DBEEEDCDDEABCEADADBEDDAAABCABEBBDABABECBECC"

    "AAECA"

    5

    Returns: 57

  12. "CACBCACCCABBCABBACBBABBBCABCCCABACB"

    "CBBCBACAAACBACBAACAABACCCAB"

    4

    Returns: 54

  13. "LDGRESFDJKCACHCDFGEBWAOTV"

    "CCWLJUMQTTTTBREXBJOHQM"

    2

    Returns: 51

  14. "EFAABEBADBBDCCCBEEADFBDAAEEBCEDBABCEAEAFDACDFAAAA"

    "FCAFFAFFBFDAABACBBAFAEFFBCECFDCEBD"

    2

    Returns: 73

  15. "CHGACCIBGEFB"

    "CCHFCECHGEABHFBBHGGGFCHCBEIFCIAEHBCFGBFBFG"

    1

    Returns: 41

  16. "RMSLGQNQQSJHNAJBFOOTDCJAFMSTTDGFBTIPP"

    "SJRLFHNLQQDMSJTSIKBKFTCKTSHQFDDLAF"

    5

    Returns: 81

  17. "KFHACKED"

    "KBAGDKFBEJBFBBDF"

    2

    Returns: 24

  18. "BAABBBABAABBAAAAABA"

    "BAABAAAABBBAAAABAAAAAAABBABBBBBBBBBBABABAABBAABAB"

    7

    Returns: 64

  19. "MDUEFDBNFPTTTBCRPKVSILSIBRLVPMLKGQLBTGJVJ"

    "IBHPNLKRHAOPIPPMUUIHSISMVUTAGNTDDSHJHUQG"

    6

    Returns: 93

  20. "DCJGDIFADCJBAFHCE"

    "IKCKK"

    7

    Returns: 36

  21. "DJMNLNPFNBGQGBMDODFGGPGNCSGFNQ"

    "PFPHTSQNGFOTN"

    3

    Returns: 46

  22. "MBDFMHFBNBCLBMDKKH"

    "I"

    8

    Returns: 35

  23. "K"

    "UPRNCIMOIRVRSNEIUMTOCBN"

    7

    Returns: 38

  24. "TNMIDHHVCVLJNQDPLVJIDSLCRJOHJSVTGUEPTC"

    "HECGIOKB"

    2

    Returns: 48

  25. "ECDKBD"

    "FCIJFACIFHFL"

    86

    Returns: 190

  26. "BHBAHGBDGEAEGIEB"

    "IBDDJCBEEIDGFCGHIEBEAHCCAGHFEJFD"

    4

    Returns: 54

  27. "FJXZHIAIVRG"

    "MTEYJLYOFFDORDPGJJZOJY"

    57

    Returns: 147

  28. "FFFBEAAADACFCAACFCBDBDCBABBBDADACDDDE"

    "AEFCABFFFAEAEBFDFAFDDAECBDDFFECCC"

    6

    Returns: 82

  29. "CDEADBCCCECABDEABDABCDDCDEBEBBECEBDBABCDABADEABA"

    "BDDAAABADBEAEADBCDAEECABCDDBABC"

    4

    Returns: 73

  30. "DACCCDBCACACDBBCACCBCDBACBDAD"

    "AABBDABDCBADDCCDBACCAA"

    7

    Returns: 65

  31. "CCBAA"

    "AABA"

    7

    Returns: 19

  32. "OMJDGSDMAOLKQBTVOOIEKOULVJIKRLLPQVJPFENTPTUGNIHHOU"

    "NGUG"

    6

    Returns: 66

  33. "DBECICFGIBEJGAIAEHGCDIHEJGHGCBJEBAJCF"

    "CAGCJCGDFAIHDDC"

    7

    Returns: 66

  34. "BJFJDOHAGEGCECJAMNMNNONOLHECCGDLKAJALDMKKJIFKB"

    "NDHF"

    2

    Returns: 54

  35. "CFAAKDJAKJDDEDJKJGIEBJFEAJBCJDCCJGE"

    "ADBDKDJBHDHIHEH"

    2

    Returns: 50

  36. "ASBLHBQAOMDSGRROOAOELACRLGJSSJKCFGKIKB"

    "IOQIPLRFBBFKBPEMDGBOARFALRPFFHSLEHHOIJPABCRBPJFPM"

    1

    Returns: 77

  37. "AAABBACABAACBBACAA"

    "CCCBAABCAAACC"

    2

    Returns: 25

  38. "BIKHD"

    "GHHFAEJBJIHEJBKFA"

    0

    Returns: 16

  39. "CCCABBEBCCCCABCAEABCCEBECDD"

    "CEBEEEECCACDCCEACBDCBEDBBBEDABA"

    0

    Returns: 26

  40. "IBGHFIGJJFBHAIDBHHHIHHEFFFCICCCEEIEDACA"

    "ADBCFIADDHGDFGBBEAIHGHFBIEIGEDIBGICEICACGA"

    5

    Returns: 88

  41. "JLVCQHTEQNGTKKSDNGPBKENRLBGGOWJCONLR"

    "NCHNWEHPUOWHQUI"

    1

    Returns: 49

  42. "PXDHLMXXAONDSOBHBKOHNFJMJ"

    "XXWRPMERMRIDTJGFTAKFEAQRWKXXGGXGLXCAXNP"

    6

    Returns: 74

  43. "CBCACDDDBACCDBACACDACCBBAB"

    "ABA"

    7

    Returns: 39

  44. "PKDNAPIFLNBFEKBEJCPENDDGKEDKAGB"

    "NGKDPAHEHIMBIIEMHGJHIE"

    3

    Returns: 57

  45. "CCBACAAC"

    "BCCCBBBCABCACCCBCBBBCBABCCBBBCCBB"

    3

    Returns: 41

  46. "NNHKHOLHJHLNHCEOCEMMPJNONCJHMNFMHAJD"

    "OOEEDELPIDNBJ"

    1

    Returns: 46

  47. "DBACABDCDBEFGCGAFABEACCFEBCEDGDDGE"

    "DAGDFCFGDFCEAFBBAGGADBDGEBECGFFCEEBAEFCCGFDG"

    5

    Returns: 83

  48. "QEEHVONHGPSOM"

    "UIUDPYGWKOD"

    18

    Returns: 60

  49. "HEISGUT"

    "NDTGTTHHISEPOKBIGAPPJR"

    6

    Returns: 41

  50. "GPCMIKGALRNOPIKINCPAFFRDRGROKM"

    "QDMSRSRRJGNMFHELINRBGHECPBLQIEF"

    3

    Returns: 67

  51. "LPAORQGUXQVVGOPACWAIZMJNGDXT"

    "BUZNOTJIHULYFAXVMRTWMPBMXQPRMTTZH"

    4

    Returns: 69

  52. "CABFBBFECFCCDEABBCGCFEDECDAFAEBECGAG"

    "EBDFBGBFFBGD"

    3

    Returns: 53

  53. "UHCLKIDHHGLNKBEGACCMLOSCGGG"

    "GPHNRKLOBQAAMSENBCMEJNSDPFSLPFSDBPVKECBCECPO"

    0

    Returns: 51

  54. "KALGKLGCKKICBLLIFGDJHKFABAHCALEGBFJBIFBKB"

    "KKIIB"

    2

    Returns: 42

  55. "WEPTOBJFWQWHOTVCFIPWV"

    "EBSQLTGDRLRXMOVOEUCCDHRPLETOIFWBOLRLRXALD"

    37

    Returns: 136

  56. "ACCACCBBBCCABAACCBBCCCBBCCAC"

    "BBABBBCCCABBBBCABABCBBBCBAAACACBAAABAAABA"

    6

    Returns: 75

  57. "MHVHPJTXUCIQIMTCGCBRHXSSA"

    "QRB"

    40

    Returns: 108

  58. "ABC"

    "ABC"

    100

    Returns: 0

  59. "ABCDE"

    "ABXDE"

    5

    Returns: 12

  60. "AAAAAAAAAAAAAAAAX"

    "BBBBBBBBBBBBBBBBBBBBBX"

    4

    Returns: 45

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: