Overview

Given a bit string \(S\) of length \(N\), count the number of pairs of contiguous substrings of the same length whose Hamming distance is exactly \(1\).

Analysis

Naive Approach and Its Limitations

If we enumerate all pairs \(((l_1, r_1), (l_2, r_2))\) by brute force, even with a fixed length \(L\), there are \(O(N^2)\) combinations of starting positions, and there are also \(O(N)\) possible lengths, resulting in an overall complexity of \(O(N^3)\) or more. This is too slow for \(N = 5000\).

Key Insight: Organizing by “Shift Amount”

Fix the difference between the starting positions of the two substrings as the shift amount \(d = l_2 - l_1\) (\(d \geq 1\)). Then, a pair of substrings of the same length \(L\) can be expressed as:

• First substring: \(S[k], S[k+1], \ldots, S[k+L-1]\)
• Second substring: \(S[k+d], S[k+d+1], \ldots, S[k+d+L-1]\)

For each position \(k\), we check whether \(S[k]\) and \(S[k+d]\) match, and enumerate the mismatch positions. The Hamming distance of the pair being \(1\) is equivalent to the interval \([k, k+L-1]\) containing exactly one mismatch position.

Counting by Each Mismatch Position

When the shift amount \(d\) is fixed, let the mismatch positions be \(p_0 < p_1 < \cdots < p_{m-1}\).

For each mismatch position \(p_j\), we count the number of intervals that contain only \(p_j\) and no other mismatch positions.

For the interval \([k, k+L-1]\) to contain only \(p_j\): - Left endpoint constraint: \(k\) must be at most \(p_j\), and to exclude the previous mismatch \(p_{j-1}\), we need \(k \geq p_{j-1} + 1\) (or \(k \geq 0\) if \(j = 0\)) - Right endpoint constraint: \(k+L-1\) must be at least \(p_j\), and to exclude the next mismatch \(p_{j+1}\), we need \(k+L-1 \leq p_{j+1} - 1\) (or \(k+L-1 \leq N-1-d\) if \(j = m-1\))

The number of choices for the left endpoint is \((p_j - \text{left\_bound} + 1)\), and the number of choices for the right endpoint is \((\text{right\_bound} - p_j + 1)\), so their product is the number of pairs corresponding to \(p_j\).

Concrete example: For \(S = \) 0110, \(d = 2\): \(S[0]\) vs \(S[2]\) (0 vs 1: mismatch), \(S[1]\) vs \(S[3]\) (1 vs 0: mismatch). Mismatch positions are \(\{0, 1\}\). For \(p_0 = 0\): left bound \(= 0\), right bound \(= 0\) (\(p_1 - 1 = 0\)), so \(1 \times 1 = 1\) pair. For \(p_1 = 1\): left bound \(= 1\) (\(p_0 + 1 = 1\)), right bound \(= 1\), so \(1 \times 1 = 1\) pair. Total: \(2\) pairs.

Algorithm

1. Try each shift amount \(d\) from \(1\) to \(N-1\).
2. For each \(d\), enumerate the mismatch positions where \(S[k] \neq S[k+d]\) for \(k = 0, 1, \ldots, N-1-d\).
3. For each mismatch position \(p_j\), compute the number of left and right choices from the adjacent mismatch positions (or boundaries), and add their product to the answer.

Complexity

• Time complexity: \(O(N^2)\) — \(O(N)\) shift amounts, with \(O(N)\) processing for each
• Space complexity: \(O(N)\) — for the list of mismatch positions

Implementation Notes

• Since pairs are counted without regard to order, iterating over only positive shift amounts (\(d \geq 1\)) naturally avoids double counting.

• Shift amounts with \(0\) mismatch positions can be skipped, avoiding unnecessary computation.

• The “left boundary” for each mismatch position is the previous mismatch position \(+ 1\), and the “right boundary” is the next mismatch position \(- 1\), which can be expressed concisely. Be careful with boundary handling (at the beginning and end).

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    S = input_data[1].decode()
    
    # For each pair of starting positions (i, j) with i < j,
    # we need to count pairs of substrings of equal length that differ in exactly 1 position.
    #
    # For a fixed shift d = j - i (where d >= 1), consider comparing S[i:] and S[i+d:].
    # Let's define for each d, the match array: match[k] = 1 if S[k] == S[k+d], else 0,
    # for k = 0, 1, ..., N-1-d.
    #
    # For two substrings (l1, r1) = (k+1, k+L) and (l2, r2) = (k+d+1, k+d+L),
    # they have Hamming distance 1 over length L iff exactly one of match[k], match[k+1], ..., match[k+L-1] is 0.
    #
    # For a fixed d, let the positions where match[k] = 0 be at indices p_0, p_1, ..., p_{m-1}.
    # A substring pair of length L starting at position k (in the first string) has exactly one mismatch
    # iff the window [k, k+L-1] contains exactly one of the p_i.
    #
    # For each consecutive pair of mismatch positions (p_{j}, p_{j+1}), and also boundaries,
    # we can count how many (k, L) windows contain exactly p_j as the only mismatch.
    #
    # Actually, let me think differently. For fixed d, let mismatch positions be p_0 < p_1 < ... < p_{m-1}.
    # The valid range for k is [0, N-d-L] and L >= 1, but it's easier to think in terms of intervals.
    #
    # For each mismatch position p_j, the window [k, k+L-1] must contain p_j but not p_{j-1} or p_{j+1}.
    # Let left_bound = p_{j-1} + 1 if j > 0 else 0
    # Let right_bound = p_{j+1} - 1 if j < m-1 else (N - 1 - d)
    # The window must satisfy: k <= p_j and k + L - 1 >= p_j,
    # also k >= left_bound and k + L - 1 <= right_bound.
    # So: left_bound <= k <= p_j and p_j <= k + L - 1 <= right_bound.
    # Let end = k + L - 1, so: k ranges in [left_bound, p_j], end ranges in [p_j, right_bound].
    # Also end >= k, which is guaranteed since end >= p_j >= k.
    # The number of (k, end) pairs = (p_j - left_bound + 1) * (right_bound - p_j + 1).
    # Each (k, end) pair corresponds to a unique (k, L) with L = end - k + 1 >= 1.
    
    total = 0
    
    for d in range(1, N):
        # Compare S[k] vs S[k+d] for k = 0, 1, ..., N-1-d
        length = N - d
        # Collect mismatch positions
        mismatches = []
        for k in range(length):
            if S[k] != S[k + d]:
                mismatches.append(k)
        
        if not mismatches:
            continue
        
        m = len(mismatches)
        max_pos = length - 1  # maximum valid index
        
        for j in range(m):
            left_bound = (mismatches[j - 1] + 1) if j > 0 else 0
            right_bound = (mismatches[j + 1] - 1) if j < m - 1 else max_pos
            
            left_count = mismatches[j] - left_bound + 1
            right_count = right_bound - mismatches[j] + 1
            
            total += left_count * right_count
    
    print(total)

solve()

---

This editorial was generated by claude4.6opus-thinking.