Count Substrings That Differ by One Character

Share

Count pairs of substrings (one from s, one from t) that differ in exactly one character.

Example 1
Input: s="aba", t="baba" → Output: 6
Example 2
Input: s="ab", t="bb" → Output: 3

Solution Approach

For each pair of starting positions (i,j), expand counting substrings differing by exactly one char.

  • For each (i,j) starting pair: expand with pointer k
  • Count chars where s[i+k] != t[j+k]
  • When diff == 1: extend as far as possible (count valid extensions)
  • When diff > 1: break
  • Add counts to result
Java
public int countSubstrings(String s, String t) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < t.length(); j++) {
            int diff = 0;
            for (int k = 0; i+k < s.length() && j+k < t.length(); k++) {
                if (s.charAt(i+k) != t.charAt(j+k)) diff++;
                if (diff == 1) count++;
                if (diff > 1) break;
            }
        }
    }
    return count;
}
  • Time Complexity: O(n*m*min(n,m))
  • Space Complexity: O(1)