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.To solve #1638 Count Substrings That Differ by One Character, the goal is to count pairs of substrings from two strings that differ by exactly one character. A useful observation is that valid substrings must match everywhere except at a single position.
A common strategy is enumeration with diagonal expansion. For every pair of starting indices in the two strings, expand both pointers simultaneously and track how many characters differ. Once the difference exceeds one, the expansion stops. Each time exactly one mismatch is seen, the substring pair contributes to the result.
A more optimized idea uses dynamic programming. For each pair of indices, track how many consecutive characters match to the left and right. When a mismatch occurs at position (i, j), the number of valid substrings using that mismatch can be computed using the lengths of matching segments around it.
This approach avoids recomputation and efficiently counts valid substrings across all alignments.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumeration with expansion | O(n * m * min(n, m)) | O(1) |
| Dynamic Programming with matching segments | O(n * m) | O(n * m) |
Fraz
Use these hints if you're stuck. Try solving on your own first.
Take every substring of s, change a character, and see how many substrings of t match that substring.
Use a Trie to store all substrings of t as a dictionary.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Dynamic programming helps reuse previously computed information about matching characters between the two strings. This reduces repeated comparisons and allows the algorithm to efficiently count valid substrings centered around mismatched positions.
Yes, string comparison and dynamic programming problems like this are common in technical interviews. Variations that involve substring comparison, mismatch counting, or two-pointer expansion frequently appear in FAANG-style interviews.
Dynamic programming tables are commonly used to store lengths of matching substrings between positions of the two strings. This helps quickly determine how many substrings can be formed when a mismatch occurs.
The optimal approach typically uses dynamic programming to track matching character segments around mismatches. By computing how many characters match to the left and right of a mismatch, you can count all valid substrings in O(n * m) time.