LeetCode 1638: Count Substrings That Differ by One Character

Question

I'm posting a solution for LeetCode's "Count Substrings That Differ by One Character". If you'd like to review, please do. Thank you!

Problem

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:

Example 2:

Constraints:

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

Code

#include <stdio.h>
#include <string.h>

static const size_t getCounts(
    const char *source,
    const char *target,
    size_t s_index,
    size_t t_index
) {
    size_t counter = 0;
    size_t prev = 0;
    size_t curr = 0;

    while (s_index < strlen(source) && t_index < strlen(target)) {
        ++curr;

        if (source[s_index] != target[t_index]) {
            prev = curr;
            curr = 0;
        }

        counter += prev;
        ++s_index;
        ++t_index;
    }

    return counter;
}

static const int countSubstrings(
    const char *source,
    const char *target
) {
    size_t counters = 0;

    for (size_t s_index = 0; s_index < strlen(source); ++s_index) {
        counters += getCounts(source, target, s_index, 0);
    }

    for (size_t t_index = 1; t_index < strlen(target); ++t_index) {
        counters += getCounts(source, target, 0, t_index);
    }

    return counters;
}

int main() {
    printf ("%i \n", countSubstrings("aba", "baba"));
    printf ("%i \n", countSubstrings("ab", "bb"));
    printf ("%i \n", countSubstrings("a", "a"));
    printf ("%i \n", countSubstrings("abe", "bbc"));
    printf ("%i \n", countSubstrings("abeaskdfjpoirgfjifjwkdafjaksld",
                                     "fqowuerflqfdjcasdjkvlfkjqheofkjsdjfasldkf"));
    return 0;
}

Outputs:

6 
3 
0 
10 
1314 

Answer 1

It looks nice, and you got the right algorithm.

Still, there are problems and additional ideas:

1. The const-qualifier on the two functions return-value is ignored. Didn't your compiler warn?

2. Denoting the start of a string-slice by pointer to start of the whole string and offset into it is cumbersome and inefficient. Just give a pointer to the start of the slice.

3. You are playing Shlemiel The Painter with all four strlen()-calls in your loops. The compiler might be able to hoist it four you, or it might not.

   If it cannot, at least those in countSubstrings() are cheaper by some constant factor than the calls to a fixed getCounts(), and thus don't influence your codes big-oh.
   But those in getCounts() turn the function from linear to quadratic, and thus the algorithm from quadratic to cubic.

   What I don't get is why you ask for the strings length at all.
   Just substitute !s[n] for strlen(s) == n.

4. Either int is always big enough, and should be used throughout, or it isn't, and you have to play it safe by using size_t.

5. By the way, the problem is symmetric in its two arguments. That can be used.

And that was all I found.

static int getCounts(const char* a, const char* b) {
    int prev = 0;
    int curr = 0;
    int r = 0;
    for (; *a && *b; r += prev) {
        ++curr;
        if (*a++ != *b++) {
            prev = curr;
            curr = 0;
        }
    }
    return r;
}

static int manyCounts(const char* a, const char* b) {
    int r = 0;
    while (*a)
        r += getCounts(a++, b);
    return r;
}

int countSubstrings(const char * a, const char * b) {
    return !*a ? 0 : manyCounts(a + 1, b) + manyCounts(b, a);
}