Overview

We count pairs of two substrings of equal length where the number of positions at which corresponding characters differ (Hamming distance) is exactly 1, without duplicates.
The key observation is that “if we fix the difference \(d\) in starting positions, the comparison becomes a problem on a single diagonal (offset).”

Analysis

Why a naive solution is too slow

There are \(O(N^2)\) substrings. The number of pairs is \(O(N^4)\), and computing the Hamming distance for each pair takes time proportional to the length, making this far too slow.

Key insight: organize by starting position difference \(d\)

If we align two substrings as: - First: \(S[l..r]\) - Second: \(S[l+d..r+d]\) (starting position shifted by \(d\))

by fixing the starting position difference \(d > 0\), the characters being compared always take the form: - \(S[i]\) vs \(S[i+d]\)

This is equivalent to “lining up and comparing characters that are distance \(d\) apart in the string.”

For \(i = 0, 1, \dots, N-d-1\), consider the array (of length \(M = N - d\)): - diff[i] = (S[i] != S[i+d]) (1 if different, 0 if same)

Then:

The Hamming distance of the pair of substrings starting at position \(i\) with length \(L\)
= the number of 1s from diff[i] to diff[i+L-1]

In other words, “Hamming distance is exactly 1” ⇔ “some interval of diff contains exactly one 1.”

Counting intervals with “exactly one 1” in diff

Let the positions where diff has a 1 be, in ascending order: $\(p_1 < p_2 < \dots < p_k\)$ (0-indexed).

The number of intervals that make \(p_j\) the “only 1 in the interval” is:

• The left endpoint can be chosen from one past the previous 1 to \(p_j\)
  Count: \(p_j - p_{j-1}\) (treating \(p_0 = -1\))
• The right endpoint can be chosen from \(p_j\) to one before the next 1
  Count: \(p_{j+1} - p_j\) (treating \(p_{k+1} = M\))

Therefore, the number of intervals where \(p_j\) is the only 1 is: $\( (p_j - p_{j-1}) (p_{j+1} - p_j) \)\( Summing this over all 1s gives the answer for that \)d$.

As for unordered pairs, any pair can be uniquely represented by choosing “the one with the smaller starting position first,” giving \(d = l_2 - l_1 > 0\). So by only considering \(d = 1, \dots, N-1\), we count without duplicates.

Algorithm

1. Initialize ans = 0.
2. For \(d = 1, 2, \dots, N-1\):
   1. Let \(M = N - d\).
   2. Store all positions \(i\) where S[i] != S[i+d] in pos (= positions of 1s in diff).
   3. Append sentinel pos.append(M) at the end (to handle the case where there is no next 1 uniformly).
   4. Set prev = -1, and for each element \(p\) in pos (excluding the last sentinel):
      • ans += (p - prev) * (next_p - p)
      • prev = p
3. Output ans.

(In the code, s is converted to bytes so that s[i] != s[i+d] comparisons are fast.)

Complexity

• Time complexity: \(O(N^2)\)
  For each \(d\), we scan \(O(N-d)\) elements, and the total is \(\sum_{d=1}^{N-1}(N-d) = O(N^2)\)
• Space complexity: \(O(N)\)
  pos has at most \(O(N)\) elements

Implementation Notes

• By adding the sentinel M at the end of pos, “the extension to the right of the last 1” can be handled with the same formula without special treatment.

• By setting prev = -1, “the extension to the left of the first 1” is handled similarly.

• The answer can become very large, but since Python’s int supports arbitrary precision, this is not an issue.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    s = input().strip().encode()

    ans = 0
    n = N
    for d in range(1, n):
        M = n - d
        pos = []
        append = pos.append
        sd = d
        for i in range(M):
            if s[i] != s[i + sd]:
                append(i)

        if pos:
            pos.append(M)  # sentinel as "second mismatch" for the last one
            prev = -1
            for idx in range(len(pos) - 1):
                p = pos[idx]
                ans += (p - prev) * (pos[idx + 1] - p)
                prev = p

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.