Strings - Count Substrings That Differ by One Character

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

Input: s="aba", t="baba" → Output: 6

Input: s="ab", t="bb" → Output: 3

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

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)