Statistics

Problem Statement for "ComplementaryDNAChains"

Problem Statement

A DNA chain is a sequence of proteins of 4 types. The types are encoded using the characters 'A', 'C', 'G', 'T'. Two proteins are called complementary if one is of type 'A' and the other is of type 'T', or if one is of type 'C' and the other is of type 'G'. Two DNA chains are called complementary if they have equal length, and the i-th protein in the first chain and the i-th protein in the second chain are complementary for all possible values of i.

You will be given Strings first and second, representing two DNA chains of equal length. Your goal is to make the two chains complementary. To do this, you can perform a number of replacements, where each replacement involves changing a single protein in either one of the chains to a different type. Return the minimum number of replacements required to achieve your goal.

Definition

Class:
ComplementaryDNAChains
Method:
minReplaces
Parameters:
String, String
Returns:
int
Method signature:
int minReplaces(String first, String second)
(be sure your method is public)

Constraints

  • first will contain between 1 and 50 characters, inclusive.
  • second will contain the same number of characters as first.
  • Each character in first and second will be 'A', 'C', 'G' or 'T'.

Examples

  1. "ACGT"

    "TGCA"

    Returns: 0

    The input DNA chains are already complementary, so no replacements are needed.

  2. "ACGT"

    "ACGT"

    Returns: 4

    We need 4 replacements to transform one of the input DNA chains to "TGCA": ACGT -> TCGT -> TGGT -> TGCT -> TGCA.

  3. "ATAGTACCAC"

    "CTTATTGGGT"

    Returns: 6

  4. "GAGCACTTGACGTTCCTAACCTGCCCTCGCCAATATTCT"

    "CGCCCACCAATGATGGCTGCAATCCTTCATGCTTGTTTC"

    Returns: 30

  5. "CCGTAAAGATTTGCCTTTATTCATA"

    "ATTCTTGTGACGCGAACGACCTTGA"

    Returns: 18

  6. "CGTTGGTGGACGAAACGCGGTCGCTCAGGAAGGTCGCCTCGCC"

    "GCTAGGCTTCTATCAGTTTACGGCCATGTAGATTTTGGTAGCC"

    Returns: 34

  7. "CTCTTGTAC"

    "TAGGCCTCA"

    Returns: 6

  8. "AAAGATCCATACTCGAATGCATCAGGAGAGAG"

    "GCGGGGCGGCCGTATAAACGTCGTAAACGTCG"

    Returns: 23

  9. "G"

    "C"

    Returns: 0

  10. "T"

    "C"

    Returns: 1

  11. "CA"

    "GT"

    Returns: 0

  12. "GA"

    "CC"

    Returns: 1

  13. "TC"

    "TG"

    Returns: 1

  14. "AA"

    "GG"

    Returns: 2

  15. "CCG"

    "GGC"

    Returns: 0

  16. "TTG"

    "TAC"

    Returns: 1

  17. "AAC"

    "TGT"

    Returns: 2

  18. "TCC"

    "CCA"

    Returns: 3

  19. "TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT"

    "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: 0

  20. "GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

    "TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT"

    Returns: 50

  21. "TGCCCAAACCGGTGACGTGGAGGGTCTGCGTCCCTAATACTAAGAAGCTA"

    "ACGGGTTTGGCCACTGCACCTCCCAGACGCAGGGATTATGATTCTTCGAT"

    Returns: 0

  22. "TAATGGTAACATGAGACATAGCTTATCTGCCAAGATGTTCGCGCAAAACA"

    "ATTACCATTGTACACTGTATCGAATAGACGGTTCTACAAGCGCGTTTTGT"

    Returns: 1

  23. "GGAAACTGCTTGTTTCATAGCCGAGTCGATAGTATATAGCGAGTCCGGGT"

    "CCTTTGACGAACAAAGTCTCGGCTCAGCTTTCATATATCGCTCAGCCCCA"

    Returns: 3

  24. "GGGCTTAGAAAGGACCCCGGTCCAAGGACAAGGCGTAAACGCGCCGAGAC"

    "TCCGAATCGTTCCTTGGGCCATGTTCCTGTTCCGCATCGGCGCTGCTCTG"

    Returns: 7

  25. "AGCCTCTCCAGCTCTATCCCGGTGAACAACGCTCTTCGTAGACACGAGTA"

    "TCGGAGAGGTCTAGATCGGCCGACTAGTTGAGAGAAGCATGTGTACTAAT"

    Returns: 9

  26. "GGGGGGTGTCCGAAACCGAGGTCCAATCGTGCCATGTAGAGCGTTAGTCA"

    "TCCGCAAAAAGCTATGGCTCGCCTCTCGCACAGTACATCTCACTATCATG"

    Returns: 17

  27. "TGCACCGTGCCCCATTGGAGCCTTTTCTCTGGATATCCACGCATAATCTG"

    "CAAATGGGAGGGATAGGTAAGCGTCCGGGCGCTAATGTCGACAATTAGTA"

    Returns: 31

  28. "CCTGATATCCGTCACTGTAGTGCTGCATTACGGCCCGCTCCATGCCCGTA"

    "TTACTGAACAAGCGCTCTGGACAGGTAGCAAGTACTAAGATTCTAAGCGG"

    Returns: 40

  29. "CTACCGCGCGCTGCTTATTAGAAGAATTCGTCGGCTCCCACAAGAGCCTG"

    "CTCCCCAGATAGGCTGTGGGATGAGACTCGGAGAGGGACGCGGCTATACT"

    Returns: 43

  30. "CTTCCCGTTATGATGTTTACCTGTTGGAGCTGCGGCTTGATTATACTAAA"

    "CGGTGTAGGATCGCTGCGGATTTCGTGCTCCTAAGTACTCCGATGAGCAA"

    Returns: 47

  31. "TAATACAAGTGACTGTACTTCAGTCATTGTGAGAGAAGCCAAGGAGAAGG"

    "GAAGGTGCGGACATAGGTGCGCTGACTGGGGGGGTGAACTGAGGAGGGGG"

    Returns: 49

  32. "GCAACTATTAAAAAATGAATAGTCGTCCAATGGCGCATCCAATCTGTTGC"

    "GTACACGTTCGAGCGTAAGTGACCTGTACCCATTGCACCTGGTATTTTGC"

    Returns: 50

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: