Counting Substrings with Only One Distinct Letter with Different Algorithms

Given a string S, return the number of substrings that have only one distinct letter.

Example 1:
Input: S = “aaaba”
Output: 8
Explanation: The substrings with one distinct letter are “aaa”, “aa”, “a”, “b”.
“aaa” occurs 1 time.
“aa” occurs 2 times.
“a” occurs 4 times.
“b” occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

Example 2:

Input: S = “aaaaaaaaaa”
Output: 55

Constraints:

1 <= S.length <= 1000
S[i] consists of only lowercase English letters.

Hints:
What if we divide the string into substrings containing only one distinct character with maximal lengths?
Now that you have sub-strings with only one distinct character, Try to come up with a formula that counts the number of its sub-strings.
Alternatively, Observe that the constraints are small so you can use brute force.

O(N^2) Bruteforce with Two Pointers: Counting SubStrings with One Unique Letter

We can do bruteforce, with two pointers. Move pointer i one-step towards the end, and pointer j (and Increment the answer) as long as S[j] is equal to S[i]. Rewind pointer j to i if j reaches the end or S[j] != S[i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int countLetters(string S) {
        int ans = 0;
        int l = S.size();
        int i = 0, j = 0;
        while (i < l) {
            while ((j < l) && (S[j] == S[i])) {
                j ++;
                ans ++;
            }
            j = ++i;            
        }
        return ans;
    }
};

class Solution {
public:
    int countLetters(string S) {
        int ans = 0;
        int l = S.size();
        int i = 0, j = 0;
        while (i < l) {
            while ((j < l) && (S[j] == S[i])) {
                j ++;
                ans ++;
            }
            j = ++i;            
        }
        return ans;
    }
};

The solution takes O(N^2) time and O(1) constant space. Since the input S length is relatively small, the bruteforce algorithm can still be used to pass all the test cases.

O(N) with Math Formulas: Combinations

Given n-size string with unique letter only, there are n*(n+1)/2 different substrings. For example:

“a”: 1 = 1 “a”
“aa”: 3 = 2 “a” + 1 + “aa”
“aaa”: 6 = 3 “a”, + 2 “aa”, + 1 “aaa”

The formula can be obtained by:

This is an improvement to the first algorithm. We are still using two pointers i and j, however, we don’t need to rewind j. Instead, we use the above math formula to compute the number of substrings and add it to the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int countLetters(string S) {
        int ans = 0;
        int i = 0, j = 0, l = S.size();
        while (i < l) {
            while ((j < l) && (S[j] == S[i])) j ++;
            int n = j - i;
            ans += (n * (n + 1) / 2);
            i = j;
        }
        return ans;
    }
};

class Solution {
public:
    int countLetters(string S) {
        int ans = 0;
        int i = 0, j = 0, l = S.size();
        while (i < l) {
            while ((j < l) && (S[j] == S[i])) j ++;
            int n = j - i;
            ans += (n * (n + 1) / 2);
            i = j;
        }
        return ans;
    }
};

The time complexity is O(N) and the space complexity is O(1) constant. The same algorithm can be implemented slightly by adding to the answers incrementally.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int countLetters(string S) {
        int n = S.size(), ans = n;
        for (int j = 0, i = 1; i < n; ++ i) {
            if (S[i] == S[j]) {
                ans += i - j;
            } else {
                j = i;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int countLetters(string S) {
        int n = S.size(), ans = n;
        for (int j = 0, i = 1; i < n; ++ i) {
            if (S[i] == S[j]) {
                ans += i - j;
            } else {
                j = i;
            }
        }
        return ans;
    }
};

The i-j adds the substrings that contain more than 1 character, and thus we need to add the n to the answer first (n times substrings of length 1)

Dynamic Programming

We can define the Dynamic Programming function F(N) as the different substrings that end the n-th character. If S[i] == S[i – 1], thus F[i] = F[i – 1] + 1, because we can have (1..i+i) or (i) solutions. Then the overall solution is to add up these numbers from F[0] to F[N-1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int countLetters(string S) {
        int n = S.size();
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++ i) {
            if (S[i] == S[i - 1]) {
                f[i] = f[i - 1] + 1;
            }
        }
        return std::accumulate(begin(f), end(f), 0, [](auto &a, auto &b) {
            return a + b;
        });
    }
};

class Solution {
public:
    int countLetters(string S) {
        int n = S.size();
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++ i) {
            if (S[i] == S[i - 1]) {
                f[i] = f[i - 1] + 1;
            }
        }
        return std::accumulate(begin(f), end(f), 0, [](auto &a, auto &b) {
            return a + b;
        });
    }
};

This DP algorithm uses O(N) space and O(N) time.

–EOF (The Ultimate Computing & Technology Blog) —