Counting Substrings with Only One Distinct Letter with Different
- 时间:2020-09-19 10:45:07
- 分类:网络文摘
- 阅读:160 次
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: 55Constraints:
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) —
推荐阅读:3 Incredible Landing Pages And What We Can Learn From Them What is Cycle Counting and How to Implement It in Your Retail Bu 4 Reasons Why Your Blog is Struggling to Find an Audience 6 Best Fashion Bloggers for Style Inspiration The Strategy You Need to Write Better Blog Posts Than Your Compe How to Improve Your Blog’s Bounce Rate (and Why You Should) Does Your SME Have A Disaster Recovery Plan? 7 Best SEO Trends Gaining Popularity In 2019 How To Choose The Best Hosting Service For A WordPress Website An Idiot’s Guide to Email Automation for Bloggers
- 评论列表
-
- 添加评论