We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Substrings That Differ by One Character

Difficulty: Medium

Problem Description

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.

Key Insights

  • A substring is a contiguous sequence of characters within a string.
  • We need to find the pairs of substrings from s and t that differ by exactly one character.
  • The problem can be solved by iterating through all possible substrings of s and t and checking for the condition of differing by one character.
  • The constraints allow for a brute-force approach due to the manageable size of input strings.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(1)

Solution

To solve the problem, we can use a brute-force approach where we generate all possible substrings of both s and t. For each substring from s, we will compare it with all substrings from t to see if they differ by exactly one character. This can be achieved by checking the characters of both substrings, counting the differences, and confirming that there is exactly one differing character.

Code Solutions

def countSubstrings(s: str, t: str) -> int:
    count = 0
    len_s, len_t = len(s), len(t)

    # Iterate over all possible substrings of s
    for i in range(len_s):
        for j in range(i + 1, len_s + 1):
            substring_s = s[i:j]
            len_sub = len(substring_s)

            # Iterate over all possible substrings of t of the same length
            for k in range(len_t - len_sub + 1):
                substring_t = t[k:k + len_sub]
                
                # Count differences
                diff_count = sum(1 for x, y in zip(substring_s, substring_t) if x != y)
                
                # Check if they differ by exactly one character
                if diff_count == 1:
                    count += 1

    return count
← Back to All Questions