Count Substrings That Differ by One Character

Count Substrings That Differ by One Character

What is this problem about?

The Count Substrings That Differ by One Character coding problem involves two strings, s and t. Your goal is to find the total number of pairs of substrings $(sub\_s, sub\_t)$ that have the same length and differ by exactly one character at exactly one position.

For example, "aba" and "aba" differ by zero characters. "aba" and "aca" differ by exactly one character at the second position. "aba" and "adc" differ by two characters. You are only interested in the "exactly one" case.

Why is this asked in interviews?

Microsoft uses this problem to test a candidate's ability to optimize nested search spaces. A brute-force approach (comparing every possible substring of every length) is extremely slow. This question evaluates whether you can use dynamic programming interview pattern or intelligent enumeration to skip redundant comparisons. It’s a great test of observational skills—noticing how character matches propagate along diagonals of a comparison matrix.

Algorithmic pattern used

This problem can be solved using Dynamic Programming or Enumeration with Expansion.

• DP Approach: You can maintain two DP tables. left[i][j] stores the length of the common prefix of suffixes $s[i \dots]$ and $t[j \dots]$. right[i][j] stores the length of the common suffix of prefixes $s[\dots i]$ and $t[\dots j]$.
• Expansion Approach: For every pair of indices $(i, j)$ in s and t where $s[i] e t[j]$, this mismatch can be the "one differing character." You then count how many matching characters are immediately to the left and how many are immediately to the right. The number of valid substring pairs for this specific mismatch is (left_matches + 1) * (right_matches + 1).

Example explanation

s = "ab", t = "bb"

1. Compare s[0] ('a') and t[0] ('b'). They differ.
   • Matches to the left: 0.
   • Matches to the right: s[1] ('b') matches t[1] ('b'). Matches = 1.
   • Substrings: (0+1) * (1+1) = 2. These are ("a", "b") and ("ab", "bb").
2. Compare s[0] ('a') and t[1] ('b'). They differ.
   • Left: 0, Right: 0. (0+1)*(0+1) = 1. Substring: ("a", "b").
3. Compare s[1] ('b') and t[0] ('b'). They match (skip). Total pairs = 3.

Common mistakes candidates make

• Overcounting: Finding the same substring pair via different mismatch points (though the logic of "differ by exactly one" usually prevents this if you only trigger on mismatches).
• Complexity issues: Using $O(N^4)$ by comparing all substrings. The goal should be $O(N^3)$ or ideally $O(N^2)$.
• Length mismatch: Forgetting that the substrings in the pair must be of equal length.

Interview preparation tip

Think of string comparison as a 2D grid where $grid[i][j]$ indicates if $s[i] == t[j]$. Most "substring match" problems involve looking at diagonal lines in this grid. Practice finding "blocks" of consecutive 1s (matches) interrupted by a single 0 (mismatch).