Watch 10 video solutions for Count Substrings That Differ by One Character, a medium level problem involving Hash Table, String, Dynamic Programming. This walkthrough by Fraz has 11,781 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.
For example, the underlined substrings in "computer" and "computation" only differ by the 'e'/'a', so this is a valid way.
Return the number of substrings that satisfy the condition above.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.
Example 2:
Input: s = "ab", t = "bb"
Output: 3
Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
("ab", "bb")
("ab", "bb")
("ab", "bb")
The underlined portions are the substrings that are chosen from s and t.
Constraints:
1 <= s.length, t.length <= 100s and t consist of lowercase English letters only.Problem Overview: Given two strings s and t, count how many substring pairs (one from each string) differ by exactly one character. The substrings must be the same length, and only a single position is allowed to mismatch.
Approach 1: Naive Approach Using Substring Comparison (O(n^3) time, O(1) space)
The brute force strategy generates every possible substring from s and t with the same length and compares them character by character. For each starting index i in s and j in t, iterate through the substring length and count mismatches. If exactly one mismatch occurs, increment the answer. This approach relies purely on string traversal and direct character comparison. While simple and easy to reason about, the repeated comparisons make the time complexity roughly O(n^3) in the worst case when many substrings share similar prefixes.
Approach 2: Optimized Approach Using Dynamic Sliding Window (O(n * m) time, O(1) space)
A more efficient strategy aligns the strings using diagonal traversal and expands a sliding window along each alignment. Start with offsets between s and t. For every aligned pair of indices, walk forward while tracking the positions of mismatches. Maintain two pointers: one marking the start of the current window and another tracking the last mismatch. When a second mismatch appears, shift the window start to the position after the previous mismatch. Every step counts how many substrings ending at the current position contain exactly one mismatch. This converts repeated substring comparisons into a single pass along each alignment. The technique combines ideas from dynamic programming and window-based enumeration over string indices, reducing the complexity to O(n * m) while using constant extra space.
Recommended for interviews: Start by explaining the brute force substring comparison since it demonstrates the core observation: count substrings with exactly one mismatch. Interviewers typically expect the optimized diagonal sliding-window method. It eliminates redundant comparisons and achieves O(n * m) time with O(1) space, which is optimal for this problem size.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Substring Comparison | O(n^3) | O(1) | Useful for understanding the problem or when input sizes are very small |
| Dynamic Sliding Window / Diagonal Traversal | O(n * m) | O(1) | Best general solution; avoids redundant substring comparisons |