Formatted question description: https://leetcode.ca/all/1638.html

# 1638. Count Substrings That Differ by One Character (Medium)

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 `"`

and __compute__r"`"`

only differ by the __computa__tion"`'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:6Explanation: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:3Explanation: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.

**Example 3:**

Input:s = "a", t = "a"Output:0

**Example 4:**

Input:s = "abe", t = "bbc"Output:10

**Constraints:**

`1 <= s.length, t.length <= 100`

`s`

and`t`

consist of lowercase English letters only.

**Related Topics**:

Hash Table, String, Trie, Rolling Hash

## Solution 1.

Intuition: We can find each pair of `s[i] != t[j]`

. Then try to extend both sides when `s[i + t] == t[j + t]`

. If we have `left`

steps extended on the left side and `right`

steps on the right side, we have `(left + 1) * (right + 1)`

options for this `{ i, j }`

case.

Example:

```
s = xbabc
t = ybbbc
```

For `i = 2`

and `j = 2`

, we have `s[i] = a`

and `t[j] = b`

that doesn’t match. Now look leftwards, we can extend left-side by 1 time due to `b`

, and extend right-side by 2 times due to `bc`

. So for this specific center `{ i = 2, j = 2 }`

, we have `2 * 3 = 6`

options.

```
// OJ: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/
// Time: O(MN * min(M, N))
// Space: O(1)
class Solution {
public:
int countSubstrings(string s, string t) {
int M = s.size(), N = t.size(), ans = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (s[i] == t[j]) continue;
int left = 1, right = 1;
while (i - left >= 0 && j - left >= 0 && s[i - left] == t[j - left]) ++left;
while (i + right < M && j + right < N && s[i + right] == t[j + right]) ++right;
ans += left * right;
}
}
return ans;
}
};
```

## Solution 2.

We can precompute the `left`

and `right`

values to save time.

```
// OJ: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int countSubstrings(string s, string t) {
int M = s.size(), N = t.size(), ans = 0, left[101][101] = {}, right[101][101] = {};
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
left[i + 1][j + 1] = s[i] == t[j] ? left[i][j] + 1 : 0;
}
}
for (int i = M - 1; i >= 0; --i) {
for (int j = N - 1; j >= 0; --j) {
right[i][j] = s[i] == t[j] ? right[i + 1][j + 1] + 1 : 0;
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (s[i] != t[j]) ans += (1 + left[i][j]) * (1 + right[i + 1][j + 1]);
}
}
return ans;
}
};
```

## Solution 3.

Consider the following `s`

and `t`

and we are using `x`

and `y`

as the differing characters.

```
s=ab[x]c
t=ab[y]c
```

When we start from `i = 0, j = 0`

, and reaches `i = 2, j = 2`

, since `s[i] != t[j]`

, `pre`

is updated as `cur = 3`

, and `cur`

is reset to `0`

. We add `3`

to the answer which covers

```
ab[x]
ab[y]
b[x]
b[y]
[x]
[y]
```

When we reach `i = 3, j = 3`

, we add `pre = 3`

to answer again, which covers

```
ab[x]c
ab[y]c
b[x]c
b[y]c
[x]c
[y]c
```

So the `pre`

is the same as the `left`

value in previous solutions. The `right`

value is achieved through adding the `pre`

value repetitively for repeating right-side characters.

The `i`

and `j`

of `helper`

function are the starting indexes of our scanning. Note that `0, 0`

should be only included once so `j`

starts from `1`

in the second loop.

```
// OJ: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/discuss/917985/JavaC%2B%2BPython-Time-O(nm)-Space-O(1)
class Solution {
int helper(string s, string t, int i, int j) {
int ans = 0, pre = 0, cur = 0;
for (int n = s.size(), m = t.size(); i < n && j < m; ++i, ++j) {
cur++;
if (s[i] != t[j]) pre = cur, cur = 0;
ans += pre;
}
return ans;
}
public:
int countSubstrings(string s, string t) {
int ans = 0 ;
for (int i = 0; i < s.size(); ++i) ans += helper(s, t, i, 0);
for (int j = 1; j < t.size(); ++j) ans += helper(s, t, 0, j);
return ans;
}
};
```

Java

```
class Solution {
public int countSubstrings(String s, String t) {
int count = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
for (int j = i + 1; j <= length; j++) {
String substr = s.substring(i, j);
count += countStrings(substr, t);
}
}
return count;
}
public int countStrings(String s, String t) {
int count = 0;
int length = s.length();
int maxStart = t.length() - length;
for (int i = 0; i <= maxStart; i++) {
if (differByOne(s, t.substring(i, i + length)))
count++;
}
return count;
}
public boolean differByOne(String s, String t) {
if (s.length() != t.length() || s.equals(t))
return false;
int differ = 0;
int length = s.length();
for (int i = 0; i < length && differ <= 1; i++) {
if (s.charAt(i) != t.charAt(i))
differ++;
}
return differ == 1;
}
}
```