Statistics

Problem Statement for "ConvertibleStrings"

Problem Statement

Let X and Y be two strings of equal length, consisting of uppercase English letters only. The two strings are called convertible if there is a permutation P of the English alphabet with the following property: if each character c in the string X is replaced by the character P(c), we obtain the string Y. (In other words, X and Y are convertible iff the following holds: whenever two letters of X are equal, the corresponding two letters of Y must be equal, and vice versa.)

For example, consider the string "ABCA". We can choose to replace each 'A' by a 'F', each 'B' by a 'B', and each 'C' by a 'G', obtaining the string "FBGF". Thus the strings "ABCA" and "FBGF" are convertible. The strings "ABCA" and "EFGH" are not convertible, because the two 'A's in the first string must correspond to the same letter in the second string. The strings "ABCA" and "EEEE" are not convertible, because different letters in the first string must correspond to different letters in the second string.

You are given two Strings A and B of the same length. These strings only contain English letters from 'A' to 'I', inclusive. (That is, only the first 9 letters of the alphabet are used.)

You want to change A and B into two strings that are convertible. The only allowed change is to choose some indices (possibly none) and to remove the characters at those indices from each of the strings. (I.e., the removed characters must be at the same positions in both strings. For example, it is not allowed to only remove character 0 of A and character 3 of B.) For example, if A="ABAC", B="AHHA" and the chosen indices are 0 and 2, then the resulting strings will be "BC" and "HA". Our goal is to choose as few indices as possible, given that after the erasing we want to obtain two convertible strings. Compute and return the smallest possible number of chosen indices.

Definition

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

Constraints

  • A will contain between 1 and 50 characters, inclusive.
  • A and B will be of the same length.
  • A will contain characters from 'A' to 'I' only.
  • B will contain characters from 'A' to 'I' only.

Examples

  1. "DD"

    "FF"

    Returns: 0

    The given strings are convertible without any removals. Any mapping with 'D' mapped to 'F' changes A to B.

  2. "AAAA"

    "ABCD"

    Returns: 3

    We can choose any three indices.

  3. "AAIAIA"

    "BCDBEE"

    Returns: 3

    One possible triple of indices is (1, 2, 5) (0-based indices).

  4. "ABACDCECDCDAAABBFBEHBDFDDHHD"

    "GBGCDCECDCHAAIBBFHEBBDFHHHHE"

    Returns: 9

  5. "H"

    "H"

    Returns: 0

  6. "GE"

    "DC"

    Returns: 0

  7. "AA"

    "AA"

    Returns: 0

  8. "BBB"

    "CAC"

    Returns: 1

  9. "FHA"

    "III"

    Returns: 2

  10. "GBFAAHIG"

    "ADEADEDG"

    Returns: 4

  11. "AAABBBAABB"

    "BABABBBABA"

    Returns: 5

  12. "CBDCBACDBD"

    "DBCCDBABAC"

    Returns: 5

  13. "AFHIHFBDIHEFIFDBEFIA"

    "FGFEFAFDCCACDBIFHEIF"

    Returns: 13

  14. "HBEFCIADAHIAEGGCGHDCE"

    "ICECEFBGIFACBIEIIHAFG"

    Returns: 12

  15. "FEDEIGCGHFFAHIEBIHFEED"

    "DCFAGGBCBAFABAIGGIAFBD"

    Returns: 13

  16. "ICEBAAHDAHBICCDDCEHIGGB"

    "EIDFGAGHBDEIAFFGIGDIHAF"

    Returns: 12

  17. "HCAIDAEHBHDCBIAIHDEHHGBF"

    "EEEAEECDBFDGHGFEFFIGFEAH"

    Returns: 13

  18. "FHDHIFFAECCAHICCDFFBFHEHB"

    "GGGHAGEIDHICFCFHEIDCDBBBH"

    Returns: 14

  19. "GAFCBDHACBGCFAICCICGHEDEHE"

    "IABCIAHIBIEAAFCDFDAHAACHGF"

    Returns: 15

  20. "ECIDGIEBFBFFFGGBAAHBFIACAFH"

    "BIGHAEBHCHAGIFHHIFBEEBHFCDC"

    Returns: 16

  21. "HIGHFCIDAAIGGABADFDBABHAIEAC"

    "DAEFBBFDHFCBHHFFFBDDHDDBDBBF"

    Returns: 18

  22. "IGIIHFCGCABFGEFCHDIDCHCDCEFEG"

    "HFHBBDDIDDCFBCHBDDDHIABFIABBB"

    Returns: 19

  23. "GEBADHGBBHCDDEFGAIBGBIHHFHGADC"

    "CGIHGBHEEDHFEFFHCAFAGGCIECAIBE"

    Returns: 19

  24. "BGGHFFDEBIEFHDDFAFHFFAAFFHEFCDG"

    "EBFDCGCIDHAIFAGGHEDFCEGFEGIFDGC"

    Returns: 19

  25. "GABFBFCIEIDEDEIBGGBCBCCDFIEHIHGC"

    "BIBDFIAFEGCDDCEHAACBCAIGDIEBAHFI"

    Returns: 19

  26. "IDCHCFHGGDBHFBEDCBCECAHBIHGHAEGCI"

    "FCCIIHBIECFFFGDAHAABCEECDCICEADAI"

    Returns: 20

  27. "BFDBEFCFFHBHHBFDCHGFBAIIFBDFEAAEAD"

    "CFHAAHAEFIGFCFBHGAIDAAAEGEGFCGDAFE"

    Returns: 22

  28. "CADEFIECDHEDCDIDGFCAEFFBGIHIIHGIBIH"

    "DGBIHADCBDAHEBFGHFAHAIDCDACFAAADBEI"

    Returns: 22

  29. "EACDBBCBFEDFAACBGDIEHFIGAGCGEDFCFCDB"

    "FDGIHEEFABIAEIAGAFICEADFECGCFIABIECH"

    Returns: 18

  30. "GFBHEIFEFBECGCDHBFIHHADCAHABHIBFHEDGC"

    "CHDIAGFGADDCHCCGIHEAGFGHEEDBHAIEECEHI"

    Returns: 25

  31. "AHEFGCBGCEBBGFEGACCDBBIAGBIBGAGICBFGHI"

    "GFCIIADCIGFICEBDFDGHEHIIHBFIAIFFHHFEGF"

    Returns: 25

  32. "CDBACCFAHIGEEIFCAIEEHFCACBBCCBAEBIGBIGI"

    "GBAFIDFHFHGAEIGHGCIFDFBFDEGBADBIBAAEIBB"

    Returns: 27

  33. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 0

  34. "BBBABAABBAABBBBAAAABAABBBBAAAAAABBBABBAAABBABBAABA"

    "BBBBBAABABBBBAABBBBAABBAABBBAAABBBAAABABAAAABBBBAB"

    Returns: 24

  35. "BBBBBABAABABBAAAABBBBABAABBBBABAABAABABABAABBBBBBA"

    "BBBBBAAAAAABBAABABBABABAABABABBBAABAAAAAABBABBBABA"

    Returns: 17

  36. "ABBAAABBBBCBABCCABBBBCBCCACBCACACCAAACBBCBCBCABBAC"

    "CBCCCBABAAACCAACCACBAABBBBCABCCBBACBACCABABCBBCACC"

    Returns: 25

  37. "CABCBABCCCBBCCABABBACAAAABCBCAACCBABAABACBCBCBCABB"

    "CCABACAACAAACABCCCCACBBACBAAABBBCBABBAAAAACCABCBAB"

    Returns: 27

  38. "CCBACBCBDADACBCBAADBCAACCACCAADBCCACBDBCBCAADBBDAC"

    "CABACABDBDADDDCBBDDBCCCDBDDCDABCBDCDCAABDDBBBACDDD"

    Returns: 33

  39. "AECCEADBECCEEADDADEDBBAEBCDEEDBDECCEDDDBEECCEDADEB"

    "EABCEBDADCEDCEAADCEABBDDBBDDACEAAAEAEBBEEABDBAABDA"

    Returns: 33

  40. "HDHIAEEFEEGGAFIHAFGIIDIAHDGIHCAFIIHHHEBBAFHHGHEAEI"

    "EEIGDIABBHECAIIICIGBEBECGGACBCIHGCEEHHGEAAECEDDFAF"

    Returns: 36

  41. "EHEBBGEBGDCADHIBAHEBHEFIADEBHAACECGIGFIFHFGACCHIHB"

    "CAGAECGBBAHGHHHGAABIDFHDHFAGDABCCIFHEGHIGACFBHFABH"

    Returns: 35

  42. "IDEGADDIIBGDAFEIBBBGAHDHEBFBICCAHBCBHBIEGFCGFEDFHD"

    "AIFACDDGEAEGGFDHCEIDCHACCIEHHCFDHEIAAAAAGHHAIBDHFF"

    Returns: 35

  43. "ABACDCECDCDAAABBFBEHBDFDDHHDGHFHEIDICIAIABCDE"

    "GBICFFBGDCHAAIBBFHEBBDFHHHHEADFGHICBBCCDAAABB"

    Returns: 27

  44. "ABACDGHACBD"

    "BCADCBDGABD"

    Returns: 6

  45. "GIEIHIGHIAGDGGIFIIACHGDEFBCACEBEFHAHAIIEFFEAAHHFEC"

    "DAGIEGGCCGIHFGBHBHFGDGHFGGGCAHHIIAEIFIBCBEEADEAHED"

    Returns: 34

  46. "AAAAABBBBBCCC"

    "BBEEEBBEEBBEE"

    Returns: 7

  47. "ACHHCEBCICBCGDHCDCDGAAIIIGECFIEFEEEGGHCCACEHGFEICA"

    "FEFEIAFFHCADGEIIEBFHFFDIAHEHHDBGFIEHBBFEBECDGFDEEB"

    Returns: 34

  48. "AAAAAAAAAABBBBBBBBBB"

    "IABCDEFGHIIABCDEFGHI"

    Returns: 17

  49. "ABCDE"

    "AAAAA"

    Returns: 4

  50. "ABABABBBB"

    "AAAAAAAAA"

    Returns: 3

  51. "AAAA"

    "BCAA"

    Returns: 2

  52. "ABCA"

    "EEEE"

    Returns: 2

  53. "ABCCDEFGCDEFGHIDDEFGCABCCFGHIDEFDEFGCF"

    "BDFCAADFCGCDEFAAAABEFGCEFGCAHIIIIBBCCA"

    Returns: 23

  54. "AAABBBB"

    "ABBBBBB"

    Returns: 2

  55. "ABACACA"

    "BBCBDBD"

    Returns: 3

  56. "AAABBB"

    "CCCCCC"

    Returns: 3

  57. "ACC"

    "BBB"

    Returns: 1

  58. "ABDEFHIABEFIHFEADFEGHABDEFHIABEFIHFEADFEGHABDEFHI"

    "BAEDFGHIIHGHIABCDBAEDFGHIIHGHIABCDBAEDFGHIIHGHIAB"

    Returns: 34

  59. "BBBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    "CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"

    Returns: 3

  60. "ABBBB"

    "EEEEE"

    Returns: 1

  61. "BI"

    "AA"

    Returns: 1

  62. "AAAAADDDDD"

    "CCBBBEFFFF"

    Returns: 3

  63. "AB"

    "CC"

    Returns: 1

  64. "AAAAAAABBBB"

    "AAAABBBAAAB"

    Returns: 5

  65. "ABCABCABCABC"

    "BAACBBCBBCBC"

    Returns: 5

  66. "AABB"

    "AAAA"

    Returns: 2

  67. "ABCDEFGHIGHIDEFDEFGHABCDEFGIIDEFDEFGHABCDEFGIEFG"

    "BCDEFGIEFGGHIDEFDEFGHABCBCDEFGHIGHIDHABCDEFGIEGI"

    Returns: 34

  68. "AAAAEEEA"

    "CBBBBBBC"

    Returns: 3

  69. "DAC"

    "HAA"

    Returns: 1

  70. "ABDGEIAEABCEDFGHIEEEEBBBBBCCCCCCCDDDDDBBBABCDEF"

    "BCEHFFCIBDCAIADBCFGHICDEFGADEFGHIEFGHICDBABCDEF"

    Returns: 33

  71. "AACCCAC"

    "IIIIIBG"

    Returns: 3

  72. "CCCBBBEEEEEF"

    "AIIIIIDDDBBB"

    Returns: 4

  73. "ABCDEFGHI"

    "ABCDEFGHI"

    Returns: 0

  74. "AAAAA"

    "BCCCB"

    Returns: 2

  75. "AAIAIA"

    "BCEEEE"

    Returns: 3

  76. "ABCCC"

    "ABBBB"

    Returns: 1

  77. "ABBBB"

    "BBBBA"

    Returns: 2

  78. "ABB"

    "AAA"

    Returns: 1

  79. "AAB"

    "CCC"

    Returns: 1

  80. "AABBCC"

    "DEFGHI"

    Returns: 3

  81. "AAIIIAA"

    "BBBBBEF"

    Returns: 3

  82. "AAA"

    "BAA"

    Returns: 1

  83. "AAABBBBBBAII"

    "CCCCCCCCCDII"

    Returns: 3

  84. "ABCABABCDAB"

    "EEDEEEEDFBG"

    Returns: 4

  85. "ABAA"

    "EEEE"

    Returns: 1

  86. "A"

    "B"

    Returns: 0

  87. "AAAAEEEA"

    "BCBBBBBC"

    Returns: 3

  88. "ABCD"

    "AAAA"

    Returns: 3

  89. "AABBC"

    "AABBA"

    Returns: 1

  90. "ABBBBCDF"

    "ADDEFDDA"

    Returns: 5

  91. "AAAAB"

    "ABCAA"

    Returns: 3

  92. "AAAACCCCCC"

    "BBBCBBBBBD"

    Returns: 4

  93. "ABCDEFGHI"

    "IHGFEDCBA"

    Returns: 0

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: