1638. Count Substrings That Differ by One Character
Problem Description
The goal of this problem is to count the number of ways in which we can select a non-empty substring from a string s
and replace exactly one character in it such that the modified substring matches some substring in another string t
. This is equivalent to finding substrings in s
that differ by precisely one character from any substring in t
.
For example, take s = "computer"
and t = "computation"
. If we look at the substring s[0:7] = "compute"
from s
, we can change the last character e
to a
, obtaining s[0:6] + 'a' = "computa"
. This new substring, computa
, is also a substring of t
, thus constituting one valid way.
The problem requires us to find the total number of such valid ways for all possible substrings in s
.
Intuition
To solve this problem efficiently, we can apply dynamic programming (DP). The intuition for using DP hinges on two key observations:
-
For every pair of indices
(i, j)
wheres[i]
is equal tot[j]
, the substrings ending at these indices can form a part of larger matching substrings, barring the one character swap. -
If
s[i]
is not equal tot[j]
, then we have found the place where a single character difference occurs. All substring pairs ending at(i, j)
and having this as their only difference should be counted.
Given these observations, we can define two DP tables:
-
f[i][j]
that stores the length of the matching substring ofs[0..i-1]
andt[0..j-1]
ending ats[i-1]
andt[j-1]
. Essentially, it tells us how far back we can extend the matching part to the left, before encountering a mismatch or the start of the strings. -
g[i][j]
serves a similar purpose but looks to the right ofi
andj
, telling us how far we can extend the matching part of the substrings starting ats[i]
andt[j]
.
The variable ans
accumulates the number of valid ways. For each mismatch found (where s[i] != t[j]
), we calculate how many valid substrings can be formed and add this to ans
. The number of valid substrings is computed as (f[i][j] + 1) * (g[i + 1][j + 1] + 1)
. This accounts for the one-character swap by combining the lengths of matching substrings directly to the left and right of (i, j)
.
We iterate through each pair of indices (i, j)
comparing characters from s
and t
, and whenever we find a mismatch, we perform the above calculation. Finally, we return the value of ans
as our answer.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution implements a dynamic programming approach to efficiently solve the problem by considering all possible substrings of s
and t
and determining if they differ by exactly one character.
Here's a step-by-step breakdown of the solution code:
-
Initialize Variables: The solution begins by initializing an accumulator
ans
to keep track of the count of valid substrings, and the lengths of the stringss
andt
, denoted asm
andn
respectively. -
Create DP Tables: Two DP tables
f
andg
are created with dimensions(m+1) x (n+1)
, initializing all their entries to0
. Each cellf[i][j]
will hold the length of the matching substring pair ending withs[i-1]
andt[j-1]
. Similarly,g[i][j]
will hold the length of the matching substring pair starting withs[i]
andt[j]
. -
Fill the
f
Table: The nested loop overi
andj
fills thef
table. For each pair(i, j)
, ifs[i-1]
is equal tot[j-1]
, thenf[i][j]
is set to the value off[i-1][j-1] + 1
, which extends the length of the matching substring by one. Otherwise,f[i][j]
is already0
, indicating no match. -
Fill the
g
Table and Calculateans
: Another nested loop, counting downwards fromm-1
to0
fori
and fromn-1
to0
forj
, fills theg
table. Ifs[i]
is equal tot[j]
, theng[i][j]
is set tog[i+1][j+1] + 1
. But whens[i]
does not matcht[j]
, a mismatch has been found. The product(f[i][j] + 1) * (g[i+1][j+1] + 1)
calculates the number of valid ways considering the mismatch as the single difference point, and this number is added to the accumulatorans
. -
Return the Result: After iterating through all possible substrings, the
ans
variable will have accumulated the total number of valid substrings where a single character replacement ins
can result in a substring int
. This accumulated result is returned as the final answer.
In this solution, dynamic programming tables f
and g
efficiently store useful computed values which are used to keep track of matches and calculate the number of possible valid substrings dynamically for each pair of indices (i,j)
. By avoiding redundant comparisons and reusing previously computed values, the algorithm avoids the naive approach's extensive computation, thus improving efficiency.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach using strings s = "acdb"
and t = "abc"
.
-
Initialize Variables: We set
ans
to 0. The lengths of the stringsm
andn
are 4 and 3 respectively. -
Create DP Tables: We initialize the DP tables
f
andg
as 5x4 matrices, ass
has length 4, andt
has length 3. -
Fill the
f
Table: We iterate through stringss
andt
with indicesi
andj
. When characters match, we setf[i][j] = f[i-1][j-1] + 1
. Here's howf
looks like after filling:a b c 0 0 0 0 a 0 1 0 0 c 0 0 0 1 d 0 0 0 0 b 0 0 1 0 -
Fill the
g
Table and Calculateans
: Next, we fill in theg
table by iterating backwards. On mismatches, we calculate(f[i][j] + 1) * (g[i+1][j+1] + 1)
and add it toans
.Steps while filling
g
:- Start at
s[3] = 'b'
andt[2] = 'c'
, no match, setg[3][2] = 0
. - Move to
s[3] = 'b'
andt[1] = 'b'
, they match, so setg[3][1] = g[4][2] + 1
which is1
. - Continue for other elements. Discrepancies are found at
s[2] = 'd'
andt[0] = 'a'
, as well ass[0] = 'a'
andt[1] = 'b'
. We calculate the valid ways for these mismatches, adding the results toans
.
Here's the
g
matrix:a b c 1 0 0 a 0 1 0 c 0 0 1 d 0 0 0 b 0 1 0 In this case,
ans
will be calculated as follows:- For
s[2] != t[0]
,(f[2][0] + 1) * (g[3][1] + 1) = (0 + 1) * (0 + 1) = 1
. - For
s[0] != t[1]
,(f[0][1] + 1) * (g[1][2] + 1) = (0 + 1) * (0 + 1) = 1
.
We add these to
ans
, getting us anans = 2
. - Start at
-
Return the Result: The variable
ans
now has the value2
, which is the number of valid substrings ins
that can match substrings int
by changing exactly one character. We return this value as the answer.
Solution Implementation
1class Solution:
2 def count_substrings(self, s: str, t: str) -> int:
3 # Initializes the count of valid substrings
4 count = 0
5 # Lengths of the input strings
6 len_s, len_t = len(s), len(t)
7 # Initialize the forward and backward match length tables
8 forward_match = [[0] * (len_t + 1) for _ in range(len_s + 1)]
9 backward_match = [[0] * (len_t + 1) for _ in range(len_s + 1)]
10
11 # Populate the forward match length table
12 for i, char_s in enumerate(s, 1):
13 for j, char_t in enumerate(t, 1):
14 if char_s == char_t:
15 forward_match[i][j] = forward_match[i - 1][j - 1] + 1
16
17 # Populate the backward match length table, and calculate the count
18 for i in range(len_s - 1, -1, -1):
19 for j in range(len_t - 1, -1, -1):
20 if s[i] == t[j]:
21 backward_match[i][j] = backward_match[i + 1][j + 1] + 1
22 else:
23 # When characters do not match, we multiply the forward match
24 # and backward match lengths and add these matched substrings to the count.
25 count += (forward_match[i][j] + 1) * (backward_match[i + 1][j + 1] + 1)
26
27 # Return the total count of valid substrings
28 return count
29
1class Solution {
2 public int countSubstrings(String s, String t) {
3 int count = 0; // Initialize count to track the number of valid substrings
4 int m = s.length(), n = t.length(); // Lengths of the input strings
5
6 // f[i][j] will store the length of the common substring of s and t ending with s[i-1] and t[j-1]
7 int[][] commonSuffixLength = new int[m + 1][n + 1];
8
9 // g[i][j] will store the length of the common substring of s and t starting with s[i] and t[j]
10 int[][] commonPrefixLength = new int[m + 1][n + 1];
11
12 // Compute the length of the common suffixes for all pairs of characters from s and t
13 for (int i = 0; i < m; i++) {
14 for (int j = 0; j < n; j++) {
15 if (s.charAt(i) == t.charAt(j)) {
16 commonSuffixLength[i + 1][j + 1] = commonSuffixLength[i][j] + 1;
17 }
18 }
19 }
20
21 // Compute the length of the common prefixes and the number of valid substrings
22 for (int i = m - 1; i >= 0; i--) {
23 for (int j = n - 1; j >= 0; j--) {
24 if (s.charAt(i) == t.charAt(j)) {
25 // If characters match, extend the common prefix by 1
26 commonPrefixLength[i][j] = commonPrefixLength[i + 1][j + 1] + 1;
27 } else {
28 // When there is a mismatch, count the valid substrings using the common prefix and suffix
29 count += (commonSuffixLength[i][j] + 1) * (commonPrefixLength[i + 1][j + 1] + 1);
30 }
31 }
32 }
33
34 return count; // Return the total count of valid substrings
35 }
36}
37
1#include <cstring>
2#include <string>
3
4class Solution {
5public:
6 // Function to count the number of good substrings.
7 int countSubstrings(string s, string t) {
8 int answer = 0; // Initialize answer to zero.
9 int m = s.length(), n = t.length(); // Get the lengths of strings s and t.
10
11 // Dynamic programming arrays to keep track of matching substrings.
12 int matchingSuffix[m + 1][n + 1];
13 int matchingPrefix[m + 1][n + 1];
14
15 // Initialize the DP tables with zeros.
16 memset(matchingSuffix, 0, sizeof(matchingSuffix));
17 memset(matchingPrefix, 0, sizeof(matchingPrefix));
18
19 // Build the DP table for suffix matching substrings.
20 for (int i = 0; i < m; ++i) {
21 for (int j = 0; j < n; ++j) {
22 if (s[i] == t[j]) {
23 // If characters match, extend the suffix by 1.
24 matchingSuffix[i + 1][j + 1] = matchingSuffix[i][j] + 1;
25 }
26 }
27 }
28
29 // Build the DP table for prefix matching substrings.
30 for (int i = m - 1; i >= 0; --i) {
31 for (int j = n - 1; j >= 0; --j) {
32 if (s[i] == t[j]) {
33 // If characters match, extend the prefix by 1.
34 matchingPrefix[i][j] = matchingPrefix[i + 1][j + 1] + 1;
35 } else {
36 // If characters don't match, calculate the count of
37 // good substrings ending here.
38 answer += (matchingSuffix[i][j] + 1) * (matchingPrefix[i + 1][j + 1] + 1);
39 }
40 }
41 }
42
43 // Return the total number of good substrings.
44 return answer;
45 }
46};
47
1// Function to count the number of good substrings.
2function countSubstrings(s: string, t: string): number {
3 let answer = 0; // Initialize answer to zero.
4 const m = s.length; // Get the length of string s.
5 const n = t.length; // Get the length of string t.
6
7 // Initialize arrays to keep track of matching substrings.
8 const matchingSuffix: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
9 const matchingPrefix: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
10
11 // Build the table for suffix matching substrings.
12 for (let i = 0; i < m; i++) {
13 for (let j = 0; j < n; j++) {
14 if (s[i] === t[j]) {
15 // If characters match, extend the suffix by 1.
16 matchingSuffix[i + 1][j + 1] = matchingSuffix[i][j] + 1;
17 }
18 }
19 }
20
21 // Build the table for prefix matching substrings.
22 for (let i = m - 1; i >= 0; i--) {
23 for (let j = n - 1; j >= 0; j--) {
24 if (s[i] === t[j]) {
25 // If characters match, extend the prefix by 1.
26 matchingPrefix[i][j] = matchingPrefix[i + 1][j + 1] + 1;
27 } else {
28 // If characters don't match, calculate the count of
29 // good substrings ending at this position.
30 answer += (matchingSuffix[i][j] + 1) * (matchingPrefix[i + 1][j + 1] + 1);
31 }
32 }
33 }
34
35 // Return the total number of good substrings.
36 return answer;
37}
38
Time and Space Complexity
Time Complexity
The given code consists of a nested loop structure, where two independent loops iterate over the length of s
and t
. The outer loop runs for m + n
times and the inner nested loops run m * n
times separately for the loops that build the f
and g
2D arrays. The computation within the inner loops operates in O(1)
time. Therefore, the total time complexity combines the O(m + n)
for the outer loops and O(m * n)
for the inner nested loops, resulting in O(m * n)
overall.
Space Complexity
The space complexity is determined by the size of the two-dimensional arrays f
and g
, each of which has a size of (m + 1) * (n + 1)
. Hence, the space used by these data structures is O(m * n)
. No other data structures are used that grow with the input size, so the total space complexity is O(m * n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the maximum element can be found in:
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!