Count Substrings That Differ by One Character

Medium

Asked by:

20 views

Topics:

Strings

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.

Example 1:

Input: s = "aba", t = "baba"
Output: 6
Explanation: The following are the pairs of substrings from s and t that differ by exactly 1 character:
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The underlined portions are the substrings that are chosen from s and t.

Example 2:

Input: s = "ab", t = "bb"
Output: 3
Explanation: The following are the pairs of substrings from s and t that differ by 1 character:
("ab", "bb")
("ab", "bb")
("ab", "bb")
The underlined portions are the substrings that are chosen from s and t.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum lengths of strings `s` and `t`? Are they of similar magnitudes or could one be significantly larger than the other?
Can the input strings `s` and `t` contain non-ASCII characters, or are they restricted to a specific character set (e.g., lowercase English letters)?
Are empty strings considered valid inputs for `s` and `t`? If either string is empty, what should the function return?
By 'substrings that differ by exactly one character', do you mean substrings of the same length in `s` and `t` that have a Hamming distance of 1?
If there are multiple substrings differing by one character, should I return all of them or just the count?

Brute Force Solution

Approach

The brute force approach here means checking every single possible substring from both input strings against each other. We will look at all possible pairs of substrings and directly compare them to see if they differ by exactly one character. If they do, we'll count it.

Here's how the algorithm would work step-by-step:

Consider every possible substring from the first string. A substring is a contiguous sequence of characters within a string. Think of it like sliding a window of different sizes across the first string.
For each of those substrings, consider every possible substring from the second string, again, like sliding a window of different sizes across the second string.
Now, take one substring from the first string and one substring from the second string and compare them.
While comparing, count how many character positions are different between the two substrings.
If the count of different character positions is exactly one, then increase our total count.
Repeat steps 3-5 for all possible pairs of substrings (one from the first string and one from the second string).
Finally, return the total count of substring pairs that differed by only one character.

Code Implementation

def count_substrings_that_differ_by_one_character(first_string, second_string):
    count = 0

    for first_string_index in range(len(first_string)):
        for second_string_index in range(len(second_string)):
            for substring_length in range(1, min(len(first_string) - first_string_index, len(second_string) - second_string_index) + 1):
                first_substring = first_string[first_string_index:first_string_index + substring_length]
                second_substring = second_string[second_string_index:second_string_index + substring_length]

                # We need to compare substrings of the same length
                if len(first_substring) == len(second_substring):
                    difference_count = 0

                    for char_index in range(len(first_substring)):
                        if first_substring[char_index] != second_substring[char_index]:
                            difference_count += 1

                    # Count if substrings differ by exactly one character
                    if difference_count == 1:
                        count += 1

    return count

Big(O) Analysis

Time Complexity

O(n^6) – The algorithm considers all possible substrings from both input strings. Generating substrings from the first string involves two nested loops (one for start index and one for length), contributing O(n^2). Similarly, generating substrings from the second string also takes O(n^2). Then, for each pair of substrings, it compares them character by character, which takes O(n) time, where n is the maximum length of the two substrings. The comparisons are nested inside the substring generation loops leading to O(n^2 * n^2 * n) time complexity. Because the string length can vary up to n, the length comparison adds another factor of n resulting in O(n^6).

Space Complexity

O(1) – The brute force approach described only uses a few integer variables to store the counts of differences and the final result. No auxiliary data structures like lists, arrays, or hash maps are created that scale with the input string lengths. The space used remains constant regardless of the size of the input strings, so the space complexity is O(1).

Optimal Solution

Approach

The most efficient way involves comparing all possible substrings of both input texts. Instead of brute-forcing every substring comparison, we focus on finding common substrings and then expanding them character by character to identify where they differ by only one character.

Here's how the algorithm would work step-by-step:

Consider all possible starting positions for substrings within both texts.
For each pair of starting positions, find the longest common substring starting at those positions.
Once a common substring is found, expand it one character at a time in both directions, checking if the expanded substrings still differ by at most one character.
Keep track of how many substring pairs that meet the condition of differing by only one character are found.
Return the total count of differing substrings.

Code Implementation

def countSubstrings(first_string, second_string):
    string1_length = len(first_string)
    string2_length = len(second_string)
    substring_count = 0

    for i in range(string1_length):
        for j in range(string2_length):
            difference_count = 0
            for substring_length in range(min(string1_length - i, string2_length - j)):
                # Increment the difference count if characters differ.
                if first_string[i + substring_length] != second_string[j + substring_length]:
                    difference_count += 1

                # If difference count equals 1, increment the substring count.
                if difference_count == 1:
                    substring_count += 1

    return substring_count

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm considers all possible starting positions for substrings in both strings, which takes O(n^2) time where n is the length of the strings. For each pair of starting positions, it finds the longest common substring and then expands it, which in the worst case could take O(n) time. Therefore, the overall time complexity is O(n^2 * n) which simplifies to O(n^3).

Space Complexity

O(1) – The described algorithm primarily uses a constant number of variables for tracking starting positions, lengths of common substrings, and a counter for differing substrings. No auxiliary data structures, like arrays or hash maps, are created to store intermediate results related to the input strings. The space used by these variables remains constant irrespective of the size of the input strings. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Both strings s and t are empty	Return 0, as there are no substrings to compare.
One string is empty, the other is not	Return 0, as no differing substrings can exist.
Strings s and t are of length 1	Compare the single characters; return 1 if they differ, 0 if they are the same.
Strings s and t are identical	Iterate and check if any substring pair differs by only one character and count those.
Strings s and t are very long (e.g., length > 1000)	Ensure the algorithm has reasonable time complexity (e.g., avoid naive O(n^4) solutions and use dynamic programming).
Strings s and t contain only identical characters (e.g., 'aaaa' and 'bbbb')	Check substring pairs of same length if they differ by exactly one character.
Strings s and t contain null characters or special characters	The solution should handle any valid character according to the language being used; otherwise, reject invalid characters explicitly.
Integer overflow when calculating the number of substrings.	Use a data type that can accommodate large numbers, such as `long` in Java or `long long` in C++.

Both strings s and t are empty

How to Handle:

Return 0, as there are no substrings to compare.

One string is empty, the other is not

How to Handle:

Return 0, as no differing substrings can exist.

Strings s and t are of length 1

How to Handle:

Compare the single characters; return 1 if they differ, 0 if they are the same.

Strings s and t are identical

How to Handle:

Iterate and check if any substring pair differs by only one character and count those.

Strings s and t are very long (e.g., length > 1000)

How to Handle:

Ensure the algorithm has reasonable time complexity (e.g., avoid naive O(n^4) solutions and use dynamic programming).

Strings s and t contain only identical characters (e.g., 'aaaa' and 'bbbb')

How to Handle:

Check substring pairs of same length if they differ by exactly one character.

Strings s and t contain null characters or special characters

How to Handle:

The solution should handle any valid character according to the language being used; otherwise, reject invalid characters explicitly.

Integer overflow when calculating the number of substrings.

How to Handle:

Use a data type that can accommodate large numbers, such as `long` in Java or `long long` in C++.