1638. Count Substrings That Differ by One Character Medium

1/**
2 * [1638] Count Substrings That Differ by One Character
3 *
4 * 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.
5 * For example, the underlined substrings in "<u>compute</u>r" and "<u>computa</u>tion" only differ by the 'e'/'a', so this is a valid way.
6 * Return the number of substrings that satisfy the condition above.
7 * A substring is a contiguous sequence of characters within a string.
8 *  
9 * Example 1:
10 * 
11 * Input: s = "aba", t = "baba"
12 * Output: 6
13 * Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
14 * ("<u>a</u>ba", "<u>b</u>aba")
15 * ("<u>a</u>ba", "ba<u>b</u>a")
16 * ("ab<u>a</u>", "<u>b</u>aba")
17 * ("ab<u>a</u>", "ba<u>b</u>a")
18 * ("a<u>b</u>a", "b<u>a</u>ba")
19 * ("a<u>b</u>a", "bab<u>a</u>")
20 * The underlined portions are the substrings that are chosen from s and t.
21 * ​​Example 2:
22 * 
23 * Input: s = "ab", t = "bb"
24 * Output: 3
25 * Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
26 * ("<u>a</u>b", "<u>b</u>b")
27 * ("<u>a</u>b", "b<u>b</u>")
28 * ("<u>ab</u>", "<u>bb</u>")
29 * ​​​​The underlined portions are the substrings that are chosen from s and t.
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	1 <= s.length, t.length <= 100
35 * 	s and t consist of lowercase English letters only.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/
41// discuss: https://leetcode.com/problems/count-substrings-that-differ-by-one-character/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn count_substrings(s: String, t: String) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_1638() {
59    }
60}
61