Count Substrings That Differ by One Character - Solution & Explanation
Problem Statement
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 <= 100sandtconsist of lowercase English letters only.
Approach Overview
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 1: Naive Approach Using Substring Comparison
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.
Complexity
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.
Approach 2: Optimized Approach Using Dynamic Sliding Window
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.
Complexity
The time complexity is generally O(n * m), which is more efficient than the naive approach. The space complexity remains O(1).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 1638 Count Substrings That Differ by One Character • Fraz • 11,859 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Substrings That Differ by One Character easy or hard?
Count Substrings That Differ by One Character Python/Java solution
How to solve Count Substrings That Differ by One Character in O(n*m)?
What is the best approach for Count Substrings That Differ by One Character?
Is Count Substrings That Differ by One Character asked at Google/Amazon/Meta?
What data structure is used in Count Substrings That Differ by One Character?
What is the time complexity of Count Substrings That Differ by One Character?
Ready to solve this problem?
Practice Count Substrings That Differ by One Character with our built-in code editor and test cases.
Practice on FleetCode