Leet code problem 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.

Flow Diagram: –

Solution: –

public int countSubstrings(String s, String t) {
        int res = 0 ;
        for (int i = 0; i < s.length(); ++i)
            res += helper(s, t, i, 0);
        for (int j = 1; j < t.length(); ++j)
            res += helper(s, t, 0, j);
        return res;
    }


    public int helper(String s, String t, int i, int j) {
        int res = 0, pre = 0, cur = 0;
        for (int n = s.length(), m = t.length(); i < n && j < m; ++i, ++j) {
            cur++;
            if (s.charAt(i) != t.charAt(j)) {
                pre = cur;
                cur = 0;
            }
            res += pre;
        }
        return res;
    }