Skip to content

1638. Count Substrings That Differ by One Character

  • Time: $O(n^2)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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