Count Substrings That Differ by One Character — Solution
Count Substrings That Differ by One Character solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Substrings That Differ by One Character is a medium coding problem on strings and dynamic programming, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 100s and t consist of lowercase English letters.
Hints for Count Substrings That Differ by One Character
Hint 1
Fix the alignment: a starting index in
sand one int.Hint 2
Walk forward from that pair of starts, counting mismatches as you extend.
Hint 3
Every prefix of the walk with exactly one mismatch is a qualifying pair; stop the walk once the count reaches two.
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
- For every start
iinsand every startjint, setdiff = 0. - Extend
kwhile both strings still have characters, incrementingdiffon a mismatch. - Break out as soon as
diffexceeds 1 — no longer extension can come back down. - Whenever
diffis 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 == 1stops too early; the run of valid lengths continues until the second mismatch. - Counting when
diff == 0includes 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 totalJava
public static int countSubstrings(String s, String t) {
int total = 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) break;
if (diff == 1) total++;
}
}
}
return total;
}C++
int countSubstrings(string s, string t) {
int total = 0;
int n = (int) s.size(), m = (int) t.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int diff = 0;
for (int k = 0; i + k < n && j + k < m; k++) {
if (s[i + k] != t[j + k]) diff++;
if (diff > 1) break;
if (diff == 1) total++;
}
}
}
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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming