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.
This approach involves generating all possible substrings of both strings s and t and then comparing them. For each pair of substrings, check if they differ by exactly one character and count those pairs.
This C solution uses nested loops to generate all pairs of substrings from strings s and t. For each pair, it uses another loop to check if the substrings differ by exactly one character, maintaining a 'miss' counter to track discrepancies. If exactly one discrepancy is found, the count is incremented. The process continues for all pairs of substrings.
The time complexity is O(n^2 * m^2), where n is the length of string s and m is the length of string t, due to the nested loops for generating and comparing substrings. The space complexity is O(1) because no additional space proportional to the input size is used.
An optimized solution is possible by using a dynamic sliding window technique. As we generate substrings of s and t with one mismatch, build them dynamically and count the substrings that are different by exactly one character.
This C solution employs a dynamic sliding window approach to count mismatches more efficiently. The loops traverse each character of both strings, using 'left' and 'right' to explore valid substrings around a mismatch. If a mismatch is found at s[i] and t[j], it calculates the number of valid substrings involving these characters.
The time complexity is generally O(n * m), which is more efficient than the naive approach. The space complexity remains O(1).
| Approach | Complexity |
|---|---|
| Naive Approach Using Substring Comparison | The time complexity is O(n^2 * m^2), where n is the length of string s and m is the length of string t, due to the nested loops for generating and comparing substrings. The space complexity is O(1) because no additional space proportional to the input size is used. |
| Optimized Approach Using Dynamic Sliding Window | The time complexity is generally O(n * m), which is more efficient than the naive approach. The space complexity remains O(1). |
| Default Approach | — |
| 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 |
Leetcode 1638 Count Substrings That Differ by One Character • Fraz • 11,781 views views
Watch 9 more video solutions →Practice Count Substrings That Differ by One Character with our built-in code editor and test cases.
Practice on FleetCode