Count Substrings That Differ by One Character — Medium Problem & Solution

Problem statement

Given strings s and t, count the pairs (substring of s, substring of t) of equal length that differ in exactly one character position.

Substrings at different positions count separately even when the text is identical.

Example 1

Input: s = "aba", t = "baba"
Output: 6
Explanation: The qualifying pairs are ("a","b") twice over, ("ab","ba"), ("ba","ab"), ("aba","bab") and ("b","a").

Example 2

Input: s = "ab", t = "bb"
Output: 3
Explanation: ("a","b"), ("ab","bb") and ("a","b") from the other alignment.

Example 3

Input: s = "a", t = "a"
Output: 0
Explanation: Identical characters differ in zero positions, not one.

Constraints

• 1 <= s.length, t.length <= 100
• s and t consist of lowercase English letters.

How to solve Count Substrings That Differ by One Character

A qualifying pair is determined by where the two substrings start and how far they extend. Fixing the two starts turns the question into a single forward scan that counts mismatches.

Approach

1. For every start i in s and every start j in t, set diff = 0.
2. Extend k while both strings still have characters, incrementing diff on a mismatch.
3. Break out as soon as diff exceeds 1 — no longer extension can come back down.
4. Whenever diff is exactly 1, the current extension is a valid pair, so count it.

Why it works

Mismatches only accumulate as the window grows, so for a fixed pair of starts the valid lengths form one contiguous run — the stretch between the first and second mismatch. Counting inside the walk enumerates exactly that run.

Complexity

• Time — O(n · m · min(n, m))
• Space — O(1)

Pitfalls

• Breaking out at diff == 1 stops too early; the run of valid lengths continues until the second mismatch.
• Counting when diff == 0 includes identical substrings, which the statement excludes.

Reference solution

Python

def countSubstrings(s: str, t: str) -> int:
    total = 0
    for i in range(len(s)):
        for j in range(len(t)):
            diff = 0
            k = 0
            while i + k < len(s) and j + k < len(t):
                if s[i + k] != t[j + k]:
                    diff += 1
                if diff > 1:
                    break
                if diff == 1:
                    total += 1
                k += 1
    return total

JavaScript

var countSubstrings = function(s, t) {
    var total = 0;
    for (var i = 0; i < s.length; i++) {
        for (var j = 0; j < t.length; j++) {
            var diff = 0;
            for (var k = 0; i + k < s.length && j + k < t.length; k++) {
                if (s.charAt(i + k) !== t.charAt(j + k)) diff++;
                if (diff > 1) break;
                if (diff === 1) total++;
            }
        }
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium