# Count Substrings That Differ by One Character
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-substrings-that-differ-by-one-character)
Canonical: https://scaleengineer.com/dsa/problems/count-substrings-that-differ-by-one-character
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Hash Table, String
---
## Problem
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
## Brute Force Enumeration of Substring Pairs
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int countSubstrings(String s, String t) {
        int m = s.length();
        int n = t.length();
        int ans = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int diff = 0;
                for (int k = 0; i + k < m && j + k < n; k++) {
                    if (s.charAt(i + k) != t.charAt(j + k)) {
                        diff++;
                    }
                    if (diff == 1) {
                        ans++;
                    }
                    if (diff > 1) {
                        break;
                    }
                }
            }
        }
        return ans;
    }
}
```
### 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`.

## Dynamic Programming
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:
1.  `match[i][j]`: Stores the length of the longest common substring ending at `s[i-1]` and `t[j-1]`.
2.  `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.
**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.
**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.
### Explanation
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]`.

```java
class Solution {
    public int countSubstrings(String s, String t) {
        int m = s.length();
        int n = t.length();
        int ans = 0;

        // match[i][j]: length of identical substring ending at s[i-1] and t[j-1]
        int[][] match = new int[m + 1][n + 1];
        // diff1[i][j]: count of 1-diff substrings ending at s[i-1] and t[j-1]
        int[][] diff1 = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    match[i][j] = match[i - 1][j - 1] + 1;
                    diff1[i][j] = diff1[i - 1][j - 1];
                } else {
                    // match[i][j] is 0 by default
                    diff1[i][j] = match[i - 1][j - 1] + 1;
                }
                ans += diff1[i][j];
            }
        }
        return ans;
    }
}
```
### 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`.

## Space-Optimized Dynamic Programming
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.
**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))`.
**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.
### Explanation
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)`.

```java
class Solution {
    public int countSubstrings(String s, String t) {
        int m = s.length();
        int n = t.length();
        int ans = 0;

        int[] match = new int[n + 1];
        int[] diff1 = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            // Store values for the (i-1, j-1) diagonal element
            int prev_row_diag_match = 0;
            int prev_row_diag_diff1 = 0;
            for (int j = 1; j <= n; j++) {
                // Before updating match[j] and diff1[j], they hold the values for row i-1.
                // We need to save them to be the 'diagonal' element for the next j.
                int temp_match = match[j];
                int temp_diff1 = diff1[j];

                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    match[j] = prev_row_diag_match + 1;
                    diff1[j] = prev_row_diag_diff1;
                } else {
                    match[j] = 0;
                    diff1[j] = prev_row_diag_match + 1;
                }
                
                ans += diff1[j];

                // Update the diagonal cache for the next j
                prev_row_diag_match = temp_match;
                prev_row_diag_diff1 = temp_diff1;
            }
        }
        return ans;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int countSubstrings(String s, String t) {
    int ans = 0;
    int m = s.length(), n = t.length();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (s.charAt(i) != t.charAt(j)) {
          int l = 0, r = 0;
          while (i - l > 0 && j - l > 0 &&
                 s.charAt(i - l - 1) == t.charAt(j - l - 1)) {
            ++l;
          }
          while (i + r + 1 < m && j + r + 1 < n &&
                 s.charAt(i + r + 1) == t.charAt(j + r + 1)) {
            ++r;
          }
          ans += (l + 1) * (r + 1);
        }
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    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

```

### CPP

```cpp
class Solution {
public:
  int countSubstrings(string s, string t) {
    int ans = 0;
    int m = s.size(), n = t.size();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (s[i] != t[j]) {
          int l = 0, r = 0;
          while (i - l > 0 && j - l > 0 && s[i - l - 1] == t[j - l - 1]) {
            ++l;
          }
          while (i + r + 1 < m && j + r + 1 < n &&
                 s[i + r + 1] == t[j + r + 1]) {
            ++r;
          }
          ans += (l + 1) * (r + 1);
        }
      }
    }
    return ans;
  }
};

```