Problem Description

Given two strings s and t of the same or different lengths, your task is to count the number of non-empty substrings that appear in both s and t such that the substrings are of the same length and differ by exactly one character at the same position.

• Each substring must be contiguous and can be of any length from 1 up to the length of s or t.
• Substrings are compared only if they are of the same length.
• We count the number of pairs (i, j, k) such that the substring of s starting at index i and the substring of t starting at index j and of length k differ by exactly one character at the same position.

Constraints:

• 1 <= s.length, t.length <= 100
• s and t consist of lowercase English letters.

Thought Process

At first glance, the problem suggests comparing all possible substrings of s and t to count how many differ by exactly one character. This brute-force approach would involve generating every possible substring pair of the same length and comparing them, which is feasible for small inputs but inefficient for larger strings.

However, since the maximum length is only 100, a more efficient solution is possible. Instead of generating all substrings, we can iterate over all possible starting positions in s and t, and for each such pair, expand to the right as long as the substrings are within bounds, counting how many positions differ. If exactly one difference is found, we increment our answer.

The key insight is that we only need to compare substrings of the same length, and we can do this efficiently by considering all possible starting indices and lengths.

Solution Approach

Let's break down the optimized approach step by step:

1. Iterate Over All Starting Positions:
   • For every index i in s and every index j in t, consider these as the starting positions of substrings to compare.
2. Expand Substrings:
   • For each pair of starting indices (i, j), expand the substrings to the right, one character at a time, as long as both indices are within their respective string bounds.
3. Count Differences:
   • While expanding, keep a count of how many positions differ between the two substrings. If the count exceeds one, stop expanding further for this pair.
   • If the count is exactly one, increment the answer by one (since we found such a substring pair).
4. Repeat for All Pairs:
   • Continue this process for all possible pairs of starting positions in s and t.

This approach avoids generating all substrings explicitly and only compares candidates as needed, making it efficient for the given constraints.

Example Walkthrough

Let's walk through an example with s = "aba" and t = "baba".

• Compare all substrings of s and t of the same length, differing by exactly one character.
• For example, compare "a" (from s) with "b" (from t): they differ by one character, so count +1.
• Compare "ab" (from s) with "ba" (from t): both positions differ, so not counted.
• Compare "ab" (from s) with "ab" (from t): no difference, not counted.
• Compare "ba" (from s) with "aa" (from t): only first character differs, count +1.
• Continue this process for all pairs.

The total count for this example is 6.

Time and Space Complexity

• Brute-force approach:
  For every possible substring in s (O(N²)), compare with every possible substring of the same length in t (O(M²)). Each comparison takes O(L) time where L is the length of the substring. This results in O(N² * M² * L) time complexity, which is inefficient.
• Optimized approach:
  For every starting pair (i, j) (O(NM)), we expand to the right at most min(N-i, M-j) steps, and stop early if more than one difference is found. In practice, this is O(N*M*L), where L is the average substring length, but since N and M are at most 100, this is efficient enough.
• Space Complexity:
  Both approaches use O(1) extra space, aside from the input strings.

Summary

The main insight is to compare all possible substrings of s and t of the same length, but to do so efficiently by expanding from all possible starting positions and counting differences on the fly. This avoids the need to generate all substrings explicitly and leverages the small input size. The solution is elegant because it directly targets the problem's "differ by exactly one character" constraint without unnecessary computation.

Code Implementation

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        ans = 0
        n, m = len(s), len(t)
        for i in range(n):
            for j in range(m):
                diff = 0
                k = 0
                while i + k < n and j + k < m:
                    if s[i + k] != t[j + k]:
                        diff += 1
                    if diff == 1:
                        ans += 1
                    elif diff > 1:
                        break
                    k += 1
        return ans
      

class Solution {
public:
    int countSubstrings(string s, string t) {
        int ans = 0, n = s.size(), m = t.size();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int diff = 0;
                for (int k = 0; i + k < n && j + k < m; ++k) {
                    if (s[i + k] != t[j + k]) ++diff;
                    if (diff == 1) ++ans;
                    else if (diff > 1) break;
                }
            }
        }
        return ans;
    }
};
      

class Solution {
    public int countSubstrings(String s, String t) {
        int ans = 0, n = s.length(), m = t.length();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int diff = 0;
                for (int k = 0; i + k < n && j + k < m; k++) {
                    if (s.charAt(i + k) != t.charAt(j + k)) diff++;
                    if (diff == 1) ans++;
                    else if (diff > 1) break;
                }
            }
        }
        return ans;
    }
}
      

var countSubstrings = function(s, t) {
    let ans = 0;
    const n = s.length, m = t.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            let diff = 0;
            let k = 0;
            while (i + k < n && j + k < m) {
                if (s[i + k] !== t[j + k]) diff++;
                if (diff === 1) ans++;
                else if (diff > 1) break;
                k++;
            }
        }
    }
    return ans;
};