Count Substrings That Differ by One Character

MediumHash TableStringDynamic ProgrammingEnumeration

Solution

export function countSubstrings(s: string, t: string): number {
  const [m, n] = [s.length, t.length];
 
  let answer = 0;
  for (let i = 0; i < m; i++) {
    answer += countSubstringsFromPosition(s, t, i, 0);
  }
  for (let j = 1; j < n; j++) {
    answer += countSubstringsFromPosition(s, t, 0, j);
  }
  return answer;
}
 
function countSubstringsFromPosition(s: string, t: string, sStart: number, tStart: number): number {
  const [m, n] = [s.length, t.length];
 
  let count = 0;
  let [prevStreak, currentStreak] = [0, 0];
  let [sIndex, tIndex] = [sStart, tStart];
 
  while (sIndex < m && tIndex < n) {
    currentStreak++;
 
    if (s[sIndex] !== t[tIndex]) {
      prevStreak = currentStreak;
      currentStreak = 0;
    }
 
    count += prevStreak;
    sIndex += 1;
    tIndex += 1;
  }
 
  return count;
}

Complexity

  • Time: O(mn)O(m \cdot n)
  • Space: O(1)O(1)