1638. Count Substrings That Differ by One Character LeetCode Solution
In this guide, you will get 1638. Count Substrings That Differ by One Character LeetCode Solution with the best time and space complexity. The solution to Count Substrings That Differ by One Character problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
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.
Constraints:
1 <= s.length, t.length <= 100
s and t consist of lowercase English letters only.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(1)
1638. Count Substrings That Differ by One Character LeetCode Solution in C++
class Solution {
public:
int countSubstrings(string s, string t) {
int ans = 0;
for (int i = 0; i < s.length(); ++i)
ans += count(s, t, i, 0);
for (int j = 1; j < t.length(); ++j)
ans += count(s, t, 0, j);
return ans;
}
private:
// Returns the number of substrings of s[i..n) and t[j..n) that differ by one
// letter.
int count(const string& s, const string& t, int i, int j) {
int res = 0;
// the number of substrings starting at s[i] and t[j] ending in the current
// index with zero different letter
int dp0 = 0;
// the number of substrings starting at s[i] and t[j] ending in the current
// index with one different letter
int dp1 = 0;
for (; i < s.length() && j < t.length(); ++i, ++j) {
if (s[i] == t[j]) {
++dp0;
} else {
dp1 = dp0 + 1;
dp0 = 0;
}
res += dp1;
}
return res;
}
}; /* code provided by PROGIEZ */
1638. Count Substrings That Differ by One Character LeetCode Solution in Java
class Solution {
public int countSubstrings(String s, String t) {
int ans = 0;
for (int i = 0; i < s.length(); ++i)
ans += count(s, t, i, 0);
for (int j = 1; j < t.length(); ++j)
ans += count(s, t, 0, j);
return ans;
}
// Returns the number of substrings of s[i..n) and t[j..n) that differ by one
// letter.
private int count(final String s, final String t, int i, int j) {
int res = 0;
// the number of substrings starting at s[i] and t[j] ending in the current
// index with zero different letter
int dp0 = 0;
// the number of substrings starting at s[i] and t[j] ending in the current
// index with one different letter
int dp1 = 0;
for (; i < s.length() && j < t.length(); ++i, ++j) {
if (s.charAt(i) == t.charAt(j)) {
++dp0;
} else {
dp1 = dp0 + 1;
dp0 = 0;
}
res += dp1;
}
return res;
}
} // code provided by PROGIEZ
1638. Count Substrings That Differ by One Character LeetCode Solution in Python
class Solution:
def countSubstrings(self, s: str, t: str) -> int:
ans = 0
for i in range(len(s)):
ans += self._count(s, t, i, 0)
for j in range(1, len(t)):
ans += self._count(s, t, 0, j)
return ans
def _count(self, s: str, t: str, i: int, j: int) -> int:
"""Returns the number of substrings of s[i..n) and t[j:] that differ by one char."""
res = 0
# the number of substrings starting at s[i] and t[j] ending in the current
# index with zero different letter
dp0 = 0
# the number of substrings starting at s[i] and t[j] ending in the current
# index with one different letter
dp1 = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
dp0 += 1
else:
dp0, dp1 = 0, dp0 + 1
res += dp1
i += 1
j += 1
return res # code by PROGIEZ
