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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Substrings That Differ by One Character

Number: 1743

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given two strings s and t, determine the number of ways to choose a non-empty substring from s and replace exactly one character (with a different character) so that the resulting substring is also a substring of t. In other words, count all pairs of substrings (one from s and one from t) that have the same length and differ by exactly one character.

Key Insights

  • Brute-forcing all substring pairs is feasible because the maximum string length is 100.
  • For each pair of starting positions in s and t, extend the substring until the characters differ.
  • Once a difference is encountered, further extension can count additional valid pairs until a second difference is encountered.
  • The approach carefully tracks when the one allowed difference occurs and stops when more than one difference is found.

Space and Time Complexity

Time Complexity: O(n * m * min(n, m)) where n and m are the lengths of s and t respectively. Space Complexity: O(1) as only a few counters and loop variables are used.

Solution

The solution uses a nested loop approach. For every possible starting index in s and every possible starting index in t, we extend the substring while tracking the number of mismatches. When a mismatch is found, it is counted as the single allowed modification. All further extensions that do not introduce an additional mismatch contribute to the count of valid substring pairs. The algorithm stops extending once a second mismatch is encountered. This guarantees that each counted pair of substrings differs by exactly one character.

Code Solutions

# Python solution with detailed comments
def countSubstrings(s: str, t: str) -> int:
    total_count = 0
    # iterate over each possible starting index in s
    for i in range(len(s)):
        # iterate over each possible starting index in t
        for j in range(len(t)):
            diff = 0  # counter for the number of different characters
            # extend the substring as long as we are within bounds
            k = 0
            while i + k < len(s) and j + k < len(t):
                # if characters differ, increase diff counter
                if s[i+k] != t[j+k]:
                    diff += 1
                # if more than one difference, break out of loop
                if diff > 1:
                    break
                # if exactly one difference, increment total count
                if diff == 1:
                    total_count += 1
                k += 1
    return total_count

# Example usage:
print(countSubstrings("aba", "baba"))  # Expected output: 6
← Back to All Questions