Count substrings that differ by one character

Hash Table String Dynamic Programming Enumeration

72.4% acceptance

Feb 25, 2026

1202

357

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. Return the number of substrings that satisfy the condition above.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_substrings(s: String, t: String) -> i32 {
    let s: Vec<u8> = s.bytes().collect();
    let t: Vec<u8> = t.bytes().collect();
    let mut count = 0;
    // For each starting pair (i, j), extend while matching and track the one diff
    for i in 0..s.len() {
      for j in 0..t.len() {
        let mut diff = 0;
        let mut k = 0;
        while i + k < s.len() && j + k < t.len() {
          if s[i + k] != t[j + k] { diff += 1; }
          if diff == 1 { count += 1; }
          if diff > 1 { break; }
          k += 1;
        }
      }
    }
    count
  }
}