Welcome to Subscribe On Youtube

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

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;
    }
};
  • 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;
        }
    }
    
    ############
    
    class Solution {
        public int countSubstrings(String s, String t) {
            int m = s.length(), n = t.length();
            int ans = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (s.charAt(i) != t.charAt(j)) {
                        int l = 1, r = 1;
                        while (i - l >= 0 && j - l >= 0 && s.charAt(i - l) == t.charAt(j - l)) {
                            ++l;
                        }
                        while (i + r < m && j + r < n && s.charAt(i + r) == t.charAt(j + r)) {
                            ++r;
                        }
                        ans += l * r;
                    }
                }
            }
            return ans;
        }
    }
    
  • // 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;
        }
    };
    
  • class Solution:
        def countSubstrings(self, s: str, t: str) -> int:
            ans = 0
            for i, a in enumerate(s):
                for j, b in enumerate(t):
                    if a != b:
                        l = r = 1
                        while i >= l and j >= l and s[i - l] == t[j - l]:
                            l += 1
                        while i + r < len(s) and j + r < len(t) and s[i + r] == t[j + r]:
                            r += 1
                        ans += l * r
            return ans
    
    ############
    
    # 1638. Count Substrings That Differ by One Character
    # https://leetcode.com/problems/count-substrings-that-differ-by-one-character/
    
    class Solution:
        def countSubstrings(self, s: str, t: str) -> int:
            if s == t: return 0
    
            res = 0
            for i in range(len(s)):
                for z in range(i+1):
                    c1 = s[i-z:i+1]
                    l = len(c1)
                    for j in range(len(t)-l+1):
                        c2 = t[j:j+l]
                        if c1 != c2 and len(c1) == len(c2) and sum(c1[i] != c2[i] for i in range(l)) == 1:
                            res += 1
                
            return res
    
  • func countSubstrings(s string, t string) (ans int) {
    	for i, a := range s {
    		for j, b := range t {
    			if a != b {
    				l, r := 1, 1
    				for i >= l && j >= l && s[i-l] == t[j-l] {
    					l++
    				}
    				for i+r < len(s) && j+r < len(t) && s[i+r] == t[j+r] {
    					r++
    				}
    				ans += l * r
    			}
    		}
    	}
    	return
    }
    

All Problems

All Solutions