Count Substrings That Differ by One Character

Med

#1504Time: O(m * n * min(m, n)) Let `m` be the length of `s` and `n` be the length of `t`. The outer loops run `m` and `n` times, respectively. The inner loop runs up to `min(m, n)` times. This results in a cubic time complexity.Space: O(1) The algorithm uses only a few variables to store indices and counts, so the space complexity is constant.

Patterns

Dynamic Programming Enumeration

Data structures

Hash Table String

Prompt

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 <= 100
s and t consist of lowercase English letters only.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible pair of substrings from s and t. We can iterate through all possible starting positions of substrings in both s and t. For each pair of starting positions, we extend the substrings one character at a time, keeping track of the number of differing characters. If the difference count is exactly one, we've found a valid pair and increment our total count. If the difference exceeds one, we can stop extending that particular pair of substrings, as any longer versions will also have more than one difference.

Algorithm

Initialize a counter ans to 0.
Get the lengths of the strings, m = s.length() and n = t.length().
Iterate through every possible starting index i for a substring in s (from 0 to m-1).
Inside this loop, iterate through every possible starting index j for a substring in t (from 0 to n-1).
For each pair of starting indices (i, j), we will compare the substrings s[i...] and t[j...] character by character.
Initialize a diff_count to 0.
Use a third loop with index k to extend the substrings. This loop runs as long as i+k < m and j+k < n.
In the k loop, compare s.charAt(i+k) and t.charAt(j+k).
If the characters are different, increment diff_count.
If diff_count becomes 1, it means the substrings s.substring(i, i+k+1) and t.substring(j, j+k+1) differ by exactly one character. This is a valid pair, so we increment ans.
If diff_count becomes greater than 1, any longer substring starting from (i, j) will also have more than one difference. We can break the inner loop over k to optimize.
After all loops complete, return ans.

Walkthrough

The algorithm uses three nested loops. The outer two loops select the starting points of substrings in s and t, respectively. The innermost loop expands these substrings and compares them character by character.

1class Solution {2    public int countSubstrings(String s, String t) {3        int m = s.length();4        int n = t.length();5        int ans = 0;6 7        for (int i = 0; i < m; i++) {8            for (int j = 0; j < n; j++) {9                int diff = 0;10                for (int k = 0; i + k < m && j + k < n; k++) {11                    if (s.charAt(i + k) != t.charAt(j + k)) {12                        diff++;13                    }14                    if (diff == 1) {15                        ans++;16                    }17                    if (diff > 1) {18                        break;19                    }20                }21            }22        }23        return ans;24    }25}

Complexity

Time

O(m * n * min(m, n)) Let `m` be the length of `s` and `n` be the length of `t`. The outer loops run `m` and `n` times, respectively. The inner loop runs up to `min(m, n)` times. This results in a cubic time complexity.

Space

O(1) The algorithm uses only a few variables to store indices and counts, so the space complexity is constant.

Trade-offs

Pros

It's straightforward to understand and implement.
It uses constant extra space, making it very memory-efficient.

Cons

The time complexity is cubic, which can be slow if the string lengths are large.
It recomputes the same information multiple times, as substrings are re-evaluated.

A more efficient method is to use dynamic programming. We can define DP states that build upon solutions to smaller subproblems. We'll use two DP tables:

match[i][j]: Stores the length of the longest common substring ending at s[i-1] and t[j-1].
diff1[i][j]: Stores the count of substring pairs ending at s[i-1] and t[j-1] that differ by exactly one character.

The total count is the sum of all values in the diff1 table. The recurrence relations depend on whether the characters s[i-1] and t[j-1] are the same.

Algorithm

Let m = s.length() and n = t.length().
Create two 2D DP arrays, match[m+1][n+1] and diff1[m+1][n+1], initialized to zeros.
match[i][j] will store the length of the identical substring ending at s[i-1] and t[j-1].
diff1[i][j] will store the number of substring pairs ending at s[i-1] and t[j-1] that differ by exactly one character.
Initialize a result variable ans = 0.
Iterate i from 1 to m and j from 1 to n.
If s.charAt(i-1) == t.charAt(j-1):
- The current characters match, so we can extend any previous identical substring. match[i][j] = match[i-1][j-1] + 1.
- We can also extend any previous 1-difference substring. diff1[i][j] = diff1[i-1][j-1].
If s.charAt(i-1) != t.charAt(j-1):
- The current characters form a mismatch. An identical substring cannot end here. match[i][j] = 0.
- A 1-difference substring ending here must have this mismatch as its only difference. The prefix must be identical. The number of such substrings is equal to the length of the identical substring ending at the previous characters (s[i-2], t[j-2]) plus one (for the single-character substring). So, diff1[i][j] = match[i-1][j-1] + 1.
In each step of the inner loop, add the newly computed diff1[i][j] to ans.
Return ans.

Walkthrough

The core idea is to build the solution by considering all possible ending positions for substrings. For each pair of indices (i, j), we calculate how many valid substring pairs end at s[i-1] and t[j-1].

1class Solution {2    public int countSubstrings(String s, String t) {3        int m = s.length();4        int n = t.length();5        int ans = 0;6 7        // match[i][j]: length of identical substring ending at s[i-1] and t[j-1]8        int[][] match = new int[m + 1][n + 1];9        // diff1[i][j]: count of 1-diff substrings ending at s[i-1] and t[j-1]10        int[][] diff1 = new int[m + 1][n + 1];11 12        for (int i = 1; i <= m; i++) {13            for (int j = 1; j <= n; j++) {14                if (s.charAt(i - 1) == t.charAt(j - 1)) {15                    match[i][j] = match[i - 1][j - 1] + 1;16                    diff1[i][j] = diff1[i - 1][j - 1];17                } else {18                    // match[i][j] is 0 by default19                    diff1[i][j] = match[i - 1][j - 1] + 1;20                }21                ans += diff1[i][j];22            }23        }24        return ans;25    }26}

Complexity

Time

O(m * n) The algorithm iterates through each cell of the DP tables once, performing constant time work at each cell. This leads to a quadratic time complexity.

Space

O(m * n) We use two 2D arrays of size `(m+1) x (n+1)` to store the DP states.

Trade-offs

Pros

Significantly more time-efficient than the brute-force approach.
The logic systematically covers all cases without redundant computations.

Cons

Requires O(m*n) extra space, which can be large for strings up to the constraint limits.

The dynamic programming approach can be further optimized in terms of space. Notice that the calculation for dp[i][j] only depends on the values from the previous row (i-1), specifically the diagonal element dp[i-1][j-1]. This means we don't need to store the entire 2D DP table. We can reduce the space complexity by only keeping track of the previous row's DP values while computing the current row.

Algorithm

The logic is the same as the standard DP approach, but we optimize space.
Let m = s.length() and n = t.length().
We only need the values from the previous row (i-1) to compute the current row (i).
Create two 1D arrays, match[n+1] and diff1[n+1], to store the DP values for the current row being processed.
Initialize ans = 0.
Iterate i from 1 to m.
Inside this loop, we need to store the (i-1, j-1) values. We can use temporary variables, say prev_row_match and prev_row_diff1, to hold the values match[j] and diff1[j] from the previous i iteration before they are updated for the current j.
Iterate j from 1 to n.
- Cache the value for (i-1, j-1), which corresponds to match[j-1] and diff1[j-1] from the previous i loop. A simpler way is to use a variable diagonal_match to store match[i-1][j-1] and diagonal_diff1 for diff1[i-1][j-1].
- Before computing dp[j] for the current row i, dp[j] holds the value for (i-1, j). The value we need for the diagonal (i-1, j-1) is what dp[j-1] was before it was updated in this j loop. We can manage this with a prev variable that tracks the dp[j-1] value of the current row before update.
Update match[j] and diff1[j] based on the same recurrence relations.
Add the new diff1[j] to ans.
Return ans.

Walkthrough

We can use two 1D arrays, one for match counts and one for diff1 counts, of size n+1. As we iterate through s (the i loop), these arrays will represent the current row of the conceptual 2D DP table. We use temporary variables to store the values from the top-left diagonal cell (i-1, j-1) needed for the current computation (i, j).

1class Solution {2    public int countSubstrings(String s, String t) {3        int m = s.length();4        int n = t.length();5        int ans = 0;6 7        int[] match = new int[n + 1];8        int[] diff1 = new int[n + 1];9 10        for (int i = 1; i <= m; i++) {11            // Store values for the (i-1, j-1) diagonal element12            int prev_row_diag_match = 0;13            int prev_row_diag_diff1 = 0;14            for (int j = 1; j <= n; j++) {15                // Before updating match[j] and diff1[j], they hold the values for row i-1.16                // We need to save them to be the 'diagonal' element for the next j.17                int temp_match = match[j];18                int temp_diff1 = diff1[j];19 20                if (s.charAt(i - 1) == t.charAt(j - 1)) {21                    match[j] = prev_row_diag_match + 1;22                    diff1[j] = prev_row_diag_diff1;23                } else {24                    match[j] = 0;25                    diff1[j] = prev_row_diag_match + 1;26                }27                28                ans += diff1[j];29 30                // Update the diagonal cache for the next j31                prev_row_diag_match = temp_match;32                prev_row_diag_diff1 = temp_diff1;33            }34        }35        return ans;36    }37}

Complexity

Time

O(m * n) The time complexity remains the same as the unoptimized DP approach because we still visit each state.

Space

O(n) We use 1D arrays of size `n+1` (where `n` is the length of `t`). If we ensure `t` is the shorter string, space can be `O(min(m, n))`.

Trade-offs

Pros

Achieves optimal time complexity.
Highly memory-efficient, using space proportional to only one dimension of the input.

Cons

The implementation is slightly more complex due to the need to manage state from the previous row and the diagonal element carefully.

Solutions

Solution

1class Solution {2public3  int countSubstrings(String s, String t) {4    int ans = 0;5    int m = s.length(), n = t.length();6    for (int i = 0; i < m; ++i) {7      for (int j = 0; j < n; ++j) {8        if (s.charAt(i) != t.charAt(j)) {9          int l = 0, r = 0;10          while (i - l > 0 && j - l > 0 &&11                 s.charAt(i - l - 1) == t.charAt(j - l - 1)) {12            ++l;13          }14          while (i + r + 1 < m && j + r + 1 < n &&15                 s.charAt(i + r + 1) == t.charAt(j + r + 1)) {16            ++r;17          }18          ans += (l + 1) * (r + 1);19        }20      }21    }22    return ans;23  }24}

1class Solution:2    def countSubstrings(self, s: str, t: str) -> int: ans = 0 m, n = len(s), len(t) for i, a in enumerate(s): for j, b in enumerate(t): if a != b: l = r = 0 while i > l and j > l and s[i - l - 1] == t[j - l - 1]: l += 1 while (i + r + 1 < m and j + r + 1 < n and s[i + r + 1] == t[j + r + 1]): r += 1 ans += (l + 1) * (r + 1) return ans

1class Solution {2public:3  int countSubstrings(string s, string t) {4    int ans = 0;5    int m = s.size(), n = t.size();6    for (int i = 0; i < m; ++i) {7      for (int j = 0; j < n; ++j) {8        if (s[i] != t[j]) {9          int l = 0, r = 0;10          while (i - l > 0 && j - l > 0 && s[i - l - 1] == t[j - l - 1]) {11            ++l;12          }13          while (i + r + 1 < m && j + r + 1 < n &&14                 s[i + r + 1] == t[j + r + 1]) {15            ++r;16          }17          ans += (l + 1) * (r + 1);18        }19      }20    }21    return ans;22  }23};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int countSubstrings(String s, String t) {4    int ans = 0;5    int m = s.length(), n = t.length();6    for (int i = 0; i < m; ++i) {7      for (int j = 0; j < n; ++j) {8        if (s.charAt(i) != t.charAt(j)) {9          int l = 0, r = 0;10          while (i - l > 0 && j - l > 0 &&11                 s.charAt(i - l - 1) == t.charAt(j - l - 1)) {12            ++l;13          }14          while (i + r + 1 < m && j + r + 1 < n &&15                 s.charAt(i + r + 1) == t.charAt(j + r + 1)) {16            ++r;17          }18          ans += (l + 1) * (r + 1);19        }20      }21    }22    return ans;23  }24}

1class Solution:2    def countSubstrings(self, s: str, t: str) -> int: ans = 0 m, n = len(s), len(t) for i, a in enumerate(s): for j, b in enumerate(t): if a != b: l = r = 0 while i > l and j > l and s[i - l - 1] == t[j - l - 1]: l += 1 while (i + r + 1 < m and j + r + 1 < n and s[i + r + 1] == t[j + r + 1]): r += 1 ans += (l + 1) * (r + 1) return ans

1class Solution {2public:3  int countSubstrings(string s, string t) {4    int ans = 0;5    int m = s.size(), n = t.size();6    for (int i = 0; i < m; ++i) {7      for (int j = 0; j < n; ++j) {8        if (s[i] != t[j]) {9          int l = 0, r = 0;10          while (i - l > 0 && j - l > 0 && s[i - l - 1] == t[j - l - 1]) {11            ++l;12          }13          while (i + r + 1 < m && j + r + 1 < n &&14                 s[i + r + 1] == t[j + r + 1]) {15            ++r;16          }17          ans += (l + 1) * (r + 1);18        }19      }20    }21    return ans;22  }23};

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.