1638. Count Substrings That Differ by One Character

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.

class Solution {
public:
    int countSubstrings(string s, string t) {
        int n = s.length(), m = t.length(), res = 0;
        int ldp[101][101] = {}, rdp[101][101] = {};
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(s[i] == t[j])
                    ldp[i+1][j+1] = ldp[i][j] + 1;
            }
        }
        for(int i = n - 1; i >= 0; i--) {
            for(int j = m - 1; j >= 0; j--) {
                if(s[i] == t[j])
                    rdp[i][j] = rdp[i+1][j+1] + 1;
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(s[i] != t[j])
                    res += (ldp[i][j] + 1) * (rdp[i+1][j+1] + 1);
            }
        }
        return res;
    }
};