Count Substrings That Differ by One Character
01 · Problem
Given two strings s and t, count the pairs (x, y) where x is a non-empty substring of s, y is a substring of t of the same length, and x and y differ in exactly one position.
Pairs are counted by position: a substring is identified by its start index and length, so the same text appearing at different places in s or t forms different pairs.
02 · Examples
s = "cd", t = "ce"
4
The qualifying pairs are ("c","e"), ("d","c"), ("d","e") and ("cd","ce"). Each pair differs in exactly one position; ("c","c") differs in none.
s = "a", t = "a"
0
The only pair is ("a", "a"), which differs in zero positions, so nothing qualifies.
s = "abc", t = "abd"
9
Of the 9 single-letter pairs, 7 differ (all except a/a and b/b). Among length-2 pairs only ("bc","bd") differs in exactly one spot, and among length-3 pairs only ("abc","abd"). Total: 7 + 1 + 1 = 9.
03 · Constraints
- 011 <= s.length <= 100
- 021 <= t.length <= 100
- 03s and t consist of lowercase English letters only
04 · Optimal complexity
- Time
- O(n * m)
- Space
- O(n * m)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.