Scale Engineer

Count Substrings That Differ by One Character

Med
#1504Time: O(m * n * min(m, n)) Let `m` be the length of `s` and `n` be the length of `t`. The outer loops run `m` and `n` times, respectively. The inner loop runs up to `min(m, n)` times. This results in a cubic time complexity.Space: O(1) The algorithm uses only a few variables to store indices and counts, so the space complexity is constant.
Patterns
Dynamic ProgrammingEnumeration
Data structures
Hash TableString

Prompt

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.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach systematically checks every possible pair of substrings from s and t. We can iterate through all possible starting positions of substrings in both s and t. For each pair of starting positions, we extend the substrings one character at a time, keeping track of the number of differing characters. If the difference count is exactly one, we've found a valid pair and increment our total count. If the difference exceeds one, we can stop extending that particular pair of substrings, as any longer versions will also have more than one difference.

Algorithm

  • Initialize a counter ans to 0.
  • Get the lengths of the strings, m = s.length() and n = t.length().
  • Iterate through every possible starting index i for a substring in s (from 0 to m-1).
  • Inside this loop, iterate through every possible starting index j for a substring in t (from 0 to n-1).
  • For each pair of starting indices (i, j), we will compare the substrings s[i...] and t[j...] character by character.
  • Initialize a diff_count to 0.
  • Use a third loop with index k to extend the substrings. This loop runs as long as i+k < m and j+k < n.
  • In the k loop, compare s.charAt(i+k) and t.charAt(j+k).
  • If the characters are different, increment diff_count.
  • If diff_count becomes 1, it means the substrings s.substring(i, i+k+1) and t.substring(j, j+k+1) differ by exactly one character. This is a valid pair, so we increment ans.
  • If diff_count becomes greater than 1, any longer substring starting from (i, j) will also have more than one difference. We can break the inner loop over k to optimize.
  • After all loops complete, return ans.

Walkthrough

The algorithm uses three nested loops. The outer two loops select the starting points of substrings in s and t, respectively. The innermost loop expands these substrings and compares them character by character.

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

Complexity

Time

O(m * n * min(m, n)) Let `m` be the length of `s` and `n` be the length of `t`. The outer loops run `m` and `n` times, respectively. The inner loop runs up to `min(m, n)` times. This results in a cubic time complexity.

Space

O(1) The algorithm uses only a few variables to store indices and counts, so the space complexity is constant.

Trade-offs

Pros

  • It's straightforward to understand and implement.

  • It uses constant extra space, making it very memory-efficient.

Cons

  • The time complexity is cubic, which can be slow if the string lengths are large.

  • It recomputes the same information multiple times, as substrings are re-evaluated.

Solutions

class Solution {public  int countSubstrings(String s, String t) {    int ans = 0;    int m = s.length(), n = t.length();    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (s.charAt(i) != t.charAt(j)) {          int l = 0, r = 0;          while (i - l > 0 && j - l > 0 &&                 s.charAt(i - l - 1) == t.charAt(j - l - 1)) {            ++l;          }          while (i + r + 1 < m && j + r + 1 < n &&                 s.charAt(i + r + 1) == t.charAt(j + r + 1)) {            ++r;          }          ans += (l + 1) * (r + 1);        }      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem