Count Substrings That Differ By One Character - Leetcode Solution

Problem Statement:

Given a string s, return the number of substrings that differ by exactly one character.

A substring is a contiguous sequence of characters within a string.

Example:

Input: s = "ab" Output: 1 Explanation: There is only one substring that can be obtained from "ab" and differs by one character.

Input: s = "aba" Output: 2 Explanation: There are two substrings that can be obtained from "aba" and differ by one character: "ab" and "ba".

Approach:

The brute-force approach is to generate all possible substrings and then compare each substring with all other substrings. The time complexity of this approach will be O(n^2) for generating all substrings and then O(n^2) for comparing each substring with all other substrings. This approach is not efficient for larger strings.

A better approach is to iterate through the string s character by character and then check which substrings differ by exacly one character. To do this, we can iterate through the string again and compare each substring with the current character.

For example, if the given string is "abcde" and we are at character 'c', then we can compare "abc" and "abd" as they differ by one character ('d' instead of 'c'). Similarly, we can compare "bcd" and "bce", "cde" and "cdf" and so on.

We can keep a count of such substrings while iterating through the string.

Algorithm:

1. Initialize a count variable to store the count of substrings.

2. Iterate through the string s character by character.

3. For each character, iterate through the string again and compare each substring with the current character.

4. If a substring differs by exactly one character, increment the count variable.

5. Return the count variable.

Code:

Here is the code in python:

class Solution: def countSubstrings(self, s: str) -> int: count = 0

    # iterate through the string character by character
    for i in range(len(s)):
        # iterate through the string again
        for j in range(i+1, len(s)+1):
            # get the substring
            substr = s[i:j]
            
            # if substring differs by exactly one character, increment count
            if self.diffByOne(substr):
                count += 1
    
    return count

def diffByOne(self, s: str) -> bool:
    # check if there is only one character difference
    diffs = 0
    for i in range(1, len(s)):
        if s[i] != s[i-1]:
            diffs += 1
            if diffs > 1:
                return False
            
    return True

Explanation:

1. We initialize the count variable to 0.

2. We iterate through the string s character by character using a for loop.

3. For each character, we iterate through the string again using another for loop starting from the current index + 1. This ensures that we only compare substrings that come after the current character.

4. We obtain the substring using s[i:j].

5. We check if the substring differs by exactly one character by calling the diffByOne function.

6. If the substring differs by exactly one character, we increment the count variable.

7. Finally, we return the count variable.

8. The diffByOne function checks if there is only one character difference in the substring. It does this by keeping a count of the number of differences encountered and returning False if the count exceeds 1.

9. If there is only one character difference in the substring, it returns True.

Time Complexity:

The time complexity of the algorithm is O(n^2) where n is the length of the string s. This is because we iterate through the string twice, once for each for loop. The inner loop runs from i+1 to n, where i is the current index in the outer loop. Therefore, the time complexity of the algorithm is O(n^2).

Space Complexity:

The space complexity of the algorithm is O(1) because we are not using any additional data structures to solve this problem.

1