Statistics

Problem Statement for "DifferentStrings"

Problem Statement

If X and Y are two Strings of equal length N, then the difference between them is defined as the number of indices i where the i-th character of X and the i-th character of Y are different. For example, the difference between the words "ant" and "art" is 1.

You are given two Strings, A and B, where the length of A is less than or equal to the length of B. You can apply an arbitrary number of operations to A, where each operation is one of the following:
  • Choose a character c and add it to the beginning of A.
  • Choose a character c and add it to the end of A.
Apply the operations in such a way that A and B have the same length and the difference between them is as small as possible. Return this minimum possible difference.

Definition

Class:
DifferentStrings
Method:
minimize
Parameters:
String, String
Returns:
int
Method signature:
int minimize(String A, String B)
(be sure your method is public)

Constraints

  • A and B will each contain between 1 and 50 characters, inclusive.
  • A and B will both contain only lowercase letters ('a'-'z').
  • The length of A will be less than or equal to the length of B.

Examples

  1. "koder"

    "topcoder"

    Returns: 1

    You can prepend "top" to "koder" and you'll get "topkoder". The difference between "topkoder" and "topcoder" is 1.

  2. "hello"

    "xello"

    Returns: 1

    A and B already have the same length so you cannot add any characters to A.

  3. "abc"

    "topabcoder"

    Returns: 0

  4. "adaabc"

    "aababbc"

    Returns: 2

  5. "giorgi"

    "igroig"

    Returns: 6

  6. "drdtlpfkemlvghprbgpxafedbwqt"

    "sxxcwniayjwmdaktqkmkbrzjlnzy"

    Returns: 28

  7. "kzmlggn"

    "egaegibovgisdrobpbrlxeqgdbicxueyqkewimbwvrhsouhuf"

    Returns: 6

  8. "ugqyfocfnfofertjgkoouxawrf"

    "csabjlcuaodfopfdvidtadakysypehhjt"

    Returns: 22

  9. "rxauzprgyyteidiyvmlchqrg"

    "aqbskipyoegcuocxfdllaanfoilhtumfvc"

    Returns: 22

  10. "yzfkatpuhpohr"

    "oitxcuzpxtsutducrotnssxtu"

    Returns: 10

  11. "kg"

    "wgykwqatsdimjnzcfyffrwjxwqzwqjufyi"

    Returns: 1

  12. "rordkdicnzobvxetra"

    "tiswyjfsbnjfcfohyqzea"

    Returns: 17

  13. "wplj"

    "phbkq"

    Returns: 4

  14. "rhusqvfvqfnqjciotwur"

    "qqixixnmrrufsxjgxznpiwymb"

    Returns: 18

  15. "hbfjhvqnpugn"

    "tgrrustdgirpyqpjaxbpe"

    Returns: 11

  16. "uljqrui"

    "huhxkdjpqoppcpwdvbunlewhux"

    Returns: 5

  17. "jhqkgujskpkgq"

    "bsqknbnorrhxjrhotcvvddenmk"

    Returns: 11

  18. "dfpkhgobmrzwjpezwcfizwmylvzszvrzzjoqswhpu"

    "mkgunsrzfkakgrpzqvartgvsorpltrophajlfhqzhseygovl"

    Returns: 38

  19. "ftvcsknw"

    "koqebmqzmhohjgkaqqd"

    Returns: 7

  20. "izhfchzyppipmuocjsonyrosqfx"

    "ydhloyffklqpmncvuihwuqjfcmbglcgh"

    Returns: 24

  21. "dckzaod"

    "eewrdqew"

    Returns: 7

  22. "kzwgbkmbrtwnjjz"

    "yxwyuyybuhrjfcmlrmfntjkgasesmzrdhx"

    Returns: 11

  23. "nvso"

    "uytrdy"

    Returns: 4

  24. "tubxprsqbllxrhgcndlhhc"

    "jwbjtkicjcmktfukmmnafdgtmrclueuamxhsv"

    Returns: 20

  25. "vbajryjo"

    "mlhnkqajvzzyofssfyljxwhvjvadlofxtoeyl"

    Returns: 6

  26. "ueiniu"

    "rmohxxhja"

    Returns: 6

  27. "kkuhylnumyazczawaezyoipolgmeqkxti"

    "yjtuykherfehmvvistqbwchxphziwumobxxtc"

    Returns: 28

  28. "hraekzfqza"

    "wftwwcpihddacuossmezlhodihbahl"

    Returns: 9

  29. "kzjwktv"

    "iivfbxkmi"

    Returns: 6

  30. "nlq"

    "dosdebh"

    Returns: 3

  31. "ubzh"

    "mexfy"

    Returns: 4

  32. "mpmlqzbktivcwspefcwtihyvlubhxs"

    "pwrtfxfksxhfxxppmytbrxfkztojiuzctvbvoll"

    Returns: 28

  33. "odwwwisftrivduagmcpfvltcwzfwh"

    "lctjbhbgzriouraqmefnaiaidgqajdbwpifliwlgatkedxse"

    Returns: 25

  34. "aor"

    "toulrdxyyiwddxji"

    Returns: 2

  35. "bf"

    "puebombnzfuiglhddncisjd"

    Returns: 1

  36. "w"

    "zm"

    Returns: 1

  37. "wxoxkpeyzgtroqxvvtuhq"

    "obgnvroeqhpmtjujgbymwmfgqmibai"

    Returns: 19

  38. "knytnbav"

    "hrzmjinmhnvdpv"

    Returns: 6

  39. "jegltnailybzzgjixqvtagmbfeclzt"

    "bmldwhyvbxusktzwfgjabpvsvzdmlzcnirauzpgbozauaknkuq"

    Returns: 26

  40. "ewgzrimuwno"

    "qhtxichvrgdvajolxlyrkmvqqppzogrwgrnwa"

    Returns: 9

  41. "s"

    "etnzezncpddjxvgnekzcocjnjyhzfzdffpxviiegjkwxh"

    Returns: 1

  42. "fzybwusaphsatthibtchuahnuijdujqncixsjqgzplidohv"

    "henqzittmovqbbwpbrszkdrpntljsdxxkarfpfzwczbwzjgjf"

    Returns: 45

  43. "gknxj"

    "etkletjnn"

    Returns: 4

  44. "yqmukbrfeffvlucxwef"

    "womthhavzwbjbyauaelhesqeibxbnipzgrpsdznraisyhrnotc"

    Returns: 17

  45. "gszilbffrq"

    "gkzdfsnvlnsdwgv"

    Returns: 8

  46. "spqfmslrrysfh"

    "ydfdicrosrdilxofpauhlpjthkykzbmpnarnbegeurkzle"

    Returns: 11

  47. "y"

    "yxnnsprvppraivwofrh"

    Returns: 0

  48. "suobkwyszevxgndtpwlfjnpjdyqnwabcpiheglrc"

    "vtzuaxlgaidmmfwxmhzmefgytkfdqvpiugxiqwzwblphbtu"

    Returns: 36

  49. "hjtyuknifbbhda"

    "ogipjyxmbsumllf"

    Returns: 14

  50. "vtnhhhzydnd"

    "irwfazhqjhhuglwvweut"

    Returns: 9

  51. "gfijpxllyhpoesvhsktyyonlqvqatuajageknokgtvg"

    "giygaebfatmrkjqsslzcritemmuaibndxyydhhrrdhl"

    Returns: 40

  52. "mbian"

    "cmqys"

    Returns: 5

  53. "xxqoxjgcuvlzzvvpeyfxbuv"

    "rvdpowbwekfacuobgtimfei"

    Returns: 23

  54. "tggcnwermqhdb"

    "ksouynrrlfmsm"

    Returns: 12

  55. "ltaigjij"

    "qitmmtww"

    Returns: 8

  56. "abcd"

    "jhhdsdsd"

    Returns: 3

  57. "abbcbcde"

    "xbabxbcbcdce"

    Returns: 3

  58. "wonokowoney"

    "wontwoneverhaa"

    Returns: 6

  59. "c"

    "ca"

    Returns: 0

  60. "abe"

    "cabc"

    Returns: 1

  61. "abca"

    "abcbddd"

    Returns: 1

  62. "hello"

    "ffffff"

    Returns: 5

  63. "abcda"

    "xyabc"

    Returns: 5

  64. "ccdd"

    "abcdef"

    Returns: 2

  65. "abd"

    "topabcoder"

    Returns: 1

  66. "hmeda"

    "ahmedaaa"

    Returns: 0

  67. "ba"

    "xxaxx"

    Returns: 1

  68. "ab"

    "bbb"

    Returns: 1

  69. "deg"

    "abcdefd"

    Returns: 1

  70. "bcd"

    "abcde"

    Returns: 0

  71. "aaa"

    "bcdrfaaabgaeg"

    Returns: 0

  72. "abb"

    "abab"

    Returns: 1

  73. "abb"

    "aaaabb"

    Returns: 0

  74. "ecdx"

    "baaeced"

    Returns: 2

  75. "fjdlsajfdsfsdlajflasdkjfsdklfj"

    "fdsafsdafsdfsdffdsafsdafdasfsdahfnjkdasfkjsd"

    Returns: 18

  76. "bsteb"

    "anstabckl"

    Returns: 2

  77. "sdfwejfjifejfilejilfjsfee"

    "wjeifjieerfijiewjiejflmxofekofmxmfioekf"

    Returns: 18

  78. "hellosdsdsdsd"

    "xxxxxxxxxxxxxellosdsdsdsdsdsdsd"

    Returns: 1

  79. "aaab"

    "baaabac"

    Returns: 0

  80. "a"

    "b"

    Returns: 1

  81. "aaaaaaaaaaaaaaaacdccdaa"

    "ccccccaaaaaaaaacccccaaaaaaddddcdaaa"

    Returns: 8

  82. "abc"

    "aabc"

    Returns: 0

  83. "abcd"

    "abcde"

    Returns: 0

  84. "x"

    "aaaaaaaaxaaaaaaaaa"

    Returns: 0

  85. "xyz"

    "abcd"

    Returns: 3

  86. "jkdnjkfdsfsdf"

    "kldjklcjklgfdgfdgdf"

    Returns: 9

  87. "bac"

    "aaba"

    Returns: 2

  88. "aabaa"

    "aababbc"

    Returns: 1

  89. "aa"

    "caac"

    Returns: 0

  90. "aaaa"

    "abba"

    Returns: 2

  91. "ccdef"

    "abcdefghi"

    Returns: 1

  92. "abc"

    "abbdbc"

    Returns: 1

  93. "tabctop"

    "tttopcbatoptt"

    Returns: 3

  94. "abc"

    "abcabcdhjdhjd"

    Returns: 0

  95. "ankne"

    "rranvneyy"

    Returns: 1

  96. "nxxcd"

    "xpxabcdx"

    Returns: 3

  97. "abc"

    "defgh"

    Returns: 3

  98. "zero"

    "fjkerop"

    Returns: 1

  99. "bc"

    "abdcd"

    Returns: 1

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: