1638. Count Substrings That Differ by One Character.md

1638. Count Substrings That Differ by One Character

---

the third one in Biweekly Contest 38.

---

Difficulty : Medium

Related Topics : HashTable、String、Trie、Rolling Hash

---

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.

---

Solution

• mine
  • Java
    • Runtime: 11 ms, faster than 57.33%, Memory Usage: 37 MB, less than 9.14% of Java online submissions

      // O(N^4)time
      // O(N)space
      public int countSubstrings(String s, String t) {
          char[] arr = s.toCharArray();
          char[] arrT = t.toCharArray();
          int res = 0;
          int n = arr.length;
          for(int i = 1; i <= n; i++){
              for(int j = 0 ; j <= n - i; j++){
                  res += getCount(j, j + i, arr, arrT);
              }
          }
          return res;
      }
      
      int getCount(int s, int e, char[] arr, char[] arrT){
          int res = 0;
          int count = e - s;
          for(int i = 0; i <= arrT.length - count; i++){
              int temp = 0;
              for(int j = 0; j < count; j++){
                  if(arr[s + j]  !=  arrT[i + j]){
                      temp++;
                  }
                  if(temp > 1) break;
              }
              if(temp == 1) res++;
          }
          return res;
      }
      
      

---

• the most votes

• Runtime: 5 ms, faster than 79.25%, Memory Usage: 36.8 MB, less than 9.14% of Java online submissions

  // O(N^3)time
  // O(1)space
  public int countSubstrings(String s, String t) {
      int res = 0;
      for (int i = 0; i < s.length(); ++i) {
          for (int j = 0; j < t.length(); ++j) {
              int miss = 0;
              for (int pos = 0; i + pos < s.length() && j + pos < t.length(); ++pos) {
                  if (s.charAt(i + pos) != t.charAt(j + pos) && ++miss > 1)
                      break;
                  res += miss;
              }
          }
      }
      return res;
  }
  

---