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
andt
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 }