Count Substrings That Differ by One Character

Count Substrings That Differ by One Character - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "ab", t = "bb"

› Output: 1

💡 Note: The substring "a" from s differs from substring "b" from t by exactly one character (a ≠ b). This is the only valid substring pair.

Example 2 — Multiple Matches

$ Input: s = "aba", t = "bab"

› Output: 6

💡 Note: Valid pairs: "a"→"b" (2 ways), "b"→"a" (2 ways), "ab"→"ba" (1 way), "ba"→"ab" (1 way). Total: 6 substring pairs with exactly one difference.

Example 3 — No Differences

$ Input: s = "ab", t = "ab"

› Output: 0

💡 Note: All corresponding substrings are identical, so no substring differs by exactly one character.

Constraints

1 ≤ s.length, t.length ≤ 100
s and t consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings s and t with characters to compare

Find Differences

Identify character positions where s[i] ≠ t[j]

Count Valid Pairs

Count substring pairs differing by exactly one character

Key Takeaway

🎯 Key Insight: Use DP to count prefix/suffix matches around each character difference

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to use dynamic programming to count matching prefixes and suffixes around each character difference position. Best approach uses DP with prefix/suffix tables to achieve optimal Time: O(nm), Space: O(nm)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Enumeration	O(n²m)	O(1)	Fix starting positions and extend character by character
Dynamic Programming with Prefix/Suffix	O(nm)	O(nm)	Use DP to count matching prefixes and suffixes around each difference position
Brute Force	O(n³m³)	O(1)	Check all substring pairs for exactly one character difference

Optimized Enumeration — Algorithm Steps

Step 1: Fix starting positions i in s and j in t
Step 2: Extend character by character, tracking matches
Step 3: Count valid substrings with exactly 1 difference

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix Positions

Choose starting positions i in s, j in t

Extend & Count

Extend while tracking differences

Valid Substrings

Count when exactly 1 difference

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s, char* t) {
    int count = 0;
    int n = strlen(s), m = strlen(t);
    
    // For each starting position pair
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // Track consecutive differences
            int diffCount = 0;
            int k = 0;
            while (i + k < n && j + k < m) {
                if (s[i + k] != t[j + k]) {
                    diffCount++;
                }
                
                // If exactly 1 difference, count this substring
                if (diffCount == 1) {
                    count++;
                }
                // If more than 1 difference, stop extending
                else if (diffCount > 1) {
                    break;
                }
                
                k++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[1001], t[1001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    
    int result = solution(s, t);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²m)

For each of n*m starting position pairs, extend up to min(n,m) characters

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler