LeetCode 1638 - Count Substrings That Differ by One Character

LeetCode Problem 1638

Difficulty: 🟡 Medium
Topics: Hash Table, String, Dynamic Programming, Enumeration

Solution

Problem Understanding

The problem asks us to count how many pairs of substrings, one taken from s and one taken from t, differ by exactly one character.

A substring is contiguous, so for a string like "abcde", valid substrings include "a", "bc", "abcd", and "cde".

We are not allowed to have zero differences or more than one difference. The two substrings must:

1. Have the same length
2. Differ at exactly one position

For example:

• "abc" and "adc" differ by exactly one character, the second character
• "abc" and "abc" differ by zero characters, so they are invalid
• "abc" and "axy" differ by two characters, so they are invalid

The task is to count every valid pair.

The constraints are small:

• 1 <= s.length, t.length <= 100

Since both strings are at most length 100, an O(n^3) or even O(n^4) solution may still be feasible. However, we should still look for a cleaner and more efficient approach.

Several edge cases are important:

• Single character strings
• Strings with all identical characters
• Strings with no matching regions
• Cases where many overlapping substrings contribute separately
• Cases where substrings differ at the first or last character

The problem guarantees that all characters are lowercase English letters, so character comparisons are straightforward.

Approaches

Brute Force Approach

The brute force idea is to generate every substring of s and every substring of t, then compare all pairs that have the same length.

For each pair:

1. Compare characters one by one
2. Count how many positions differ
3. If the difference count equals exactly one, increment the answer

This works because it explicitly checks every possible valid substring pair.

However, the complexity becomes expensive.

If n = len(s) and m = len(t):

• There are O(n^2) substrings in s
• There are O(m^2) substrings in t
• Comparing two substrings may take O(min(n, m))

Overall complexity becomes approximately O(n^3 * m^3) in the worst case, which is unnecessarily slow even for moderate input sizes.

Optimal Approach

The key insight is that instead of generating substrings explicitly, we can treat every pair of indices (i, j) as a potential mismatch position.

Suppose:

• s[i] != t[j]

Then this differing character can serve as the single required mismatch.

Now we only need to determine:

• How many equal characters extend to the left
• How many equal characters extend to the right

If:

• left = number of matching characters immediately to the left
• right = number of matching characters immediately to the right

Then:

• We can choose any prefix length from 0 to left
• We can choose any suffix length from 0 to right

So the number of valid substring pairs contributed by mismatch (i, j) is:

$$(left + 1) \times (right + 1)$$

This works because every constructed substring pair contains exactly one mismatch, at (i, j).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³ × m³)	O(1)	Enumerates all substring pairs explicitly
Optimal	O(n² × m²)	O(1)	Treats each mismatch as the unique differing position

Algorithm Walkthrough

Optimal Algorithm

1. Initialize answer = 0.
2. Iterate through every index i in string s.
3. Iterate through every index j in string t.
4. If s[i] == t[j], skip this pair because we need exactly one differing character.
5. If s[i] != t[j], treat (i, j) as the unique mismatch position.
6. Expand leftward:

• Start from i - 1 and j - 1
• Count how many consecutive characters match
• Store this count in left

7. Expand rightward:

• Start from i + 1 and j + 1
• Count how many consecutive characters match
• Store this count in right

8. The mismatch position itself must always be included.

• We can extend left by 0 through left characters
• We can extend right by 0 through right characters

9. Add:

$$(left + 1) \times (right + 1)$$

to the answer. 10. Continue until all index pairs are processed. 11. Return the final answer.

Why it works

Every valid substring pair has exactly one differing position. Our algorithm enumerates that differing position directly.

For each mismatch (i, j):

• left + 1 represents all valid ways to extend left while preserving equality
• right + 1 represents all valid ways to extend right while preserving equality

Multiplying them counts every substring pair whose only mismatch occurs at (i, j).

No valid pair is missed, and no invalid pair is counted twice.

Python Solution

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        answer = 0

        for i in range(n):
            for j in range(m):
                if s[i] == t[j]:
                    continue

                left = 0
                a = i - 1
                b = j - 1

                while a >= 0 and b >= 0 and s[a] == t[b]:
                    left += 1
                    a -= 1
                    b -= 1

                right = 0
                a = i + 1
                b = j + 1

                while a < n and b < m and s[a] == t[b]:
                    right += 1
                    a += 1
                    b += 1

                answer += (left + 1) * (right + 1)

        return answer

The implementation follows the algorithm directly.

The outer two loops enumerate every pair of positions (i, j).

Whenever characters differ, we treat that location as the single mismatch. We then expand outward in both directions to count matching regions.

The left expansion determines how many characters can safely be included before the mismatch. The right expansion determines how many characters can safely be included after the mismatch.

Finally, multiplying the number of left choices and right choices gives the total number of valid substring pairs centered around that mismatch.

The algorithm uses only constant extra space because all computations are performed with integer counters and index variables.

Go Solution

func countSubstrings(s string, t string) int {
	n := len(s)
	m := len(t)

	answer := 0

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {

			if s[i] == t[j] {
				continue
			}

			left := 0
			a, b := i-1, j-1

			for a >= 0 && b >= 0 && s[a] == t[b] {
				left++
				a--
				b--
			}

			right := 0
			a, b = i+1, j+1

			for a < n && b < m && s[a] == t[b] {
				right++
				a++
				b++
			}

			answer += (left + 1) * (right + 1)
		}
	}

	return answer
}

The Go implementation mirrors the Python logic closely.

Since strings in Go are byte slices for ASCII characters, direct indexing with s[i] and t[j] works correctly because the input contains only lowercase English letters.

No additional memory allocations are required, and integer overflow is not a concern because the maximum answer is well within Go's integer range for the given constraints.

Worked Examples

Example 1

s = "aba"
t = "baba"

We examine all mismatching positions.

Mismatch at s[0] = 'a' and t[0] = 'b'

Direction	Matching Count
Left	0
Right	2

Right expansion:

• s[1] == t[1] → 'b' == 'a' → no

Actually:

• right = 0

Contribution:

$$(0 + 1)(0 + 1) = 1$$

Mismatch at s[0] = 'a' and t[1] = 'a'

Characters are equal, skip.

Mismatch at s[0] = 'a' and t[2] = 'b'

Left expansion:

• none

Right expansion:

• s[1] == t[3]
• 'b' == 'a' → no

Contribution:

$$1 \times 1 = 1$$

Continuing this process for all mismatches produces the final answer:

6

Example 2

s = "ab"
t = "bb"

Mismatch at s[0]='a', t[0]='b'

Left matches: 0

Right matches:

• s[1] == t[1]
• 'b' == 'b'
• right = 1

Contribution:

$$(0+1)(1+1)=2$$

These correspond to:

• "a" vs "b"
• "ab" vs "bb"

Mismatch at s[0]='a', t[1]='b'

Left matches: 0

Right matches: 0

Contribution:

$$1$$

Total:

$$2 + 1 = 3$$

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² × m²)	Each mismatch may expand in both directions
Space	O(1)	Only a few integer variables are used

Although the nested loops iterate over all index pairs, the expansion cost is bounded by the maximum string lengths. Since the constraints are only 100, this solution performs comfortably within limits.

Test Cases

sol = Solution()

assert sol.countSubstrings("aba", "baba") == 6  # provided example
assert sol.countSubstrings("ab", "bb") == 3  # provided example

assert sol.countSubstrings("a", "a") == 0  # identical single chars
assert sol.countSubstrings("a", "b") == 1  # single mismatch

assert sol.countSubstrings("aa", "bb") == 4  # every single-char pair differs

assert sol.countSubstrings("abc", "abc") == 6  # many one-char differences in longer substrings

assert sol.countSubstrings("abcd", "efgh") == 16  # all single-char substrings differ

assert sol.countSubstrings("aaa", "aaa") == 0  # completely identical strings

assert sol.countSubstrings("abab", "baba") > 0  # overlapping matching regions

assert sol.countSubstrings("x", "yyyy") == 4  # one char against repeated chars

assert sol.countSubstrings("leetcode", "practice") > 0  # general stress case

Test Summary

Test	Why
"aba", "baba"	Validates overlapping substring counting
"ab", "bb"	Validates right-side expansion
"a", "a"	Ensures zero mismatches are excluded
"a", "b"	Smallest valid mismatch case
"aa", "bb"	All single-character mismatches
"abc", "abc"	Identical strings still produce valid differing substrings
"abcd", "efgh"	No matching regions anywhere
"aaa", "aaa"	Fully equal strings
"abab", "baba"	Repeated overlapping structures
"x", "yyyy"	Different string lengths
"leetcode", "practice"	Larger mixed-content test

Edge Cases

Completely Identical Strings

If s and t are identical, it is easy to accidentally count substrings with zero differences.

For example:

s = "aaa"
t = "aaa"

Every substring pair matches perfectly, but the problem requires exactly one differing character.

The implementation handles this correctly because it only starts expansion when s[i] != t[j].

Single Character Strings

The smallest inputs can expose off-by-one errors.

Example:

s = "a"
t = "b"

There are no left or right expansions possible, but the mismatch itself forms one valid substring pair.

The formula:

$$(left + 1)(right + 1)$$

correctly becomes:

$$1 \times 1 = 1$$

Mismatch at String Boundaries

The mismatch may occur at the beginning or end of a substring.

Example:

s = "abc"
t = "xbc"

The differing character appears at the first position.

The implementation safely handles this because the left expansion immediately stops when indices become negative, while right expansion continues normally.

Multiple Overlapping Valid Substrings

Some inputs contain many overlapping valid substrings.

Example:

s = "abab"
t = "baba"

Different substring pairs may share the same mismatch position while having different lengths.

The multiplication:

$$(left + 1)(right + 1)$$

correctly counts every distinct extension combination independently.