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 "_compute_ r" and "_computa_ tion" 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


    
    
    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:
    ("_a_ ba", "_b_ aba")
    ("_a_ ba", "ba _b_ a")
    ("ab _a_ ", "_b_ aba")
    ("ab _a_ ", "ba _b_ a")
    ("a _b_ a", "b _a_ ba")
    ("a _b_ a", "bab _a_ ")
    The underlined portions are the substrings that are chosen from s and t.
    

​​```

#### Example 2

```d

    
    
    Input: s = "ab", t = "bb"
    Output: 3
    Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
    ("_a_ b", "_b_ b")
    ("_a_ b", "b _b_ ")
    ("_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.

Solution

Method 1 – Enumerate All Pairs with One Difference

Intuition

We want to count all pairs of substrings (one from s, one from t) of the same length that differ by exactly one character. For each possible starting position in s and t, we can compare substrings character by character and count those with exactly one mismatch.

Approach

  1. For each possible starting index i in s and j in t, compare substrings starting at i and j.
  2. For each length, count the number of substrings that differ by exactly one character.
  3. For each pair, increment the answer if there is exactly one mismatch.
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

type Solution struct{}
func (Solution) CountSubstrings(s, t string) int {
    n, m := len(s), len(t)
    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            diff := 0
            for k := 0; i+k < n && j+k < m; k++ {
                if s[i+k] != t[j+k] {
                    diff++
                }
                if diff > 1 {
                    break
                }
                if diff == 1 {
                    ans++
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

class Solution {
    fun countSubstrings(s: String, t: String): Int {
        val n = s.length
        val m = t.length
        var ans = 0
        for (i in 0 until n) {
            for (j in 0 until m) {
                var diff = 0
                for (k in 0 until minOf(n-i, m-j)) {
                    if (s[i+k] != t[j+k]) diff++
                    if (diff > 1) break
                    if (diff == 1) ans++
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        ans = 0
        for i in range(n):
            for j in range(m):
                diff = 0
                for k in range(min(n - i, m - j)):
                    if s[i + k] != t[j + k]:
                        diff += 1
                    if diff > 1:
                        break
                    if diff == 1:
                        ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn count_substrings(s: String, t: String) -> i32 {
        let n = s.len();
        let m = t.len();
        let s = s.as_bytes();
        let t = t.as_bytes();
        let mut ans = 0;
        for i in 0..n {
            for j in 0..m {
                let mut diff = 0;
                for k in 0..std::cmp::min(n-i, m-j) {
                    if s[i+k] != t[j+k] {
                        diff += 1;
                    }
                    if diff > 1 {
                        break;
                    }
                    if diff == 1 {
                        ans += 1;
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    countSubstrings(s: string, t: string): number {
        const n = s.length, m = t.length;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            for (let j = 0; j < m; ++j) {
                let diff = 0;
                for (let k = 0; i + k < n && j + k < m; ++k) {
                    if (s[i + k] !== t[j + k]) diff++;
                    if (diff > 1) break;
                    if (diff === 1) ans++;
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3) in the worst case, where n is the length of s or t, since we check all pairs of substrings.
  • 🧺 Space complexity: O(1), only counters are used.