DNA Complement Matching

Problem Statement

In DNA, bases pair as A–T and C–G. Given a strand s of characters A, C, G, T, check whether it is a reverse-complement palindrome: reading one direction and complementing equals reading the other direction. Equivalently, for every pair of symmetric positions, the two bases must be complementary.

Example

Input:  s = "ACGT"
Output: true
Explanation: A pairs with T (ends) and C pairs with G (middle).

Two Pointer Approach

Set two pointers at the ends. At each step, confirm that s[left] and s[right] are a valid complementary pair using a small lookup table, then move both inward. If any pair fails, the strand is not a valid reverse complement.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def is_reverse_complement(s):
    pair = {'A': 'T', 'T': 'A', 'C': 'G', 'G': 'C'}
    left, right = 0, len(s) - 1
    while left <= right:
        if pair.get(s[left]) != s[right]:
            return False
        left += 1
        right -= 1
    return True

Java

boolean isReverseComplement(String s) {
    Map<Character, Character> pair = Map.of('A','T','T','A','C','G','G','C');
    int left = 0, right = s.length() - 1;
    while (left <= right) {
        Character comp = pair.get(s.charAt(left));
        if (comp == null || comp != s.charAt(right)) return false;
        left++; right--;
    }
    return true;
}

C++

bool isReverseComplement(string s) {
    unordered_map<char, char> pair = {{'A','T'},{'T','A'},{'C','G'},{'G','C'}};
    int left = 0, right = s.size() - 1;
    while (left <= right) {
        if (!pair.count(s[left]) || pair[s[left]] != s[right]) return false;
        left++; right--;
    }
    return true;
}

Key Takeaways

• A complement table makes the pair check O(1).
• Using left <= right also validates the middle base of odd-length strands.
• This is the opposite-direction two pointer with a custom match rule instead of equality.