반응형
https://leetcode.com/problems/count-number-of-homogenous-substrings/description
Count Number of Homogenous Substrings - LeetCode
Can you solve this real interview question? Count Number of Homogenous Substrings - Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 109 + 7. A string is homogenous if all the characters
leetcode.com
길이 n의 부분 문자열이 연속되는 문자로 이루어져있다면, 1+2+...+n개 만큼 만들어질 수 있습니다.
class Solution {
public:
int countHomogenous(string s) {
int cnt = 1, res = 1;
for(int i=1; i<s.size(); i++) {
if(s[i - 1] == s[i]) {
cnt++;
} else {
cnt = 1;
}
res = (res + cnt) % 1000000007;
}
return res;
}
};
class Solution {
public:
int countHomogenous(string s) {
s.push_back(' ');
int cnt = 1, res = 0;
for(int i=1; i<s.size(); i++) {
if(s[i - 1] == s[i]) {
cnt++;
} else {
res = (res + sumOfOneToN(cnt)) % 1000000007;
cnt = 1;
}
}
return res;
}
private:
long long sumOfOneToN(int n) {
return ((long long) n * (n + 1) / 2);
}
};반응형
'Algorithm' 카테고리의 다른 글
| LeetCode 2642. Design Graph With Shortest Path Calculator (0) | 2023.11.11 |
|---|---|
| LeetCode 1743. Restore the Array From Adjacent Pairs (0) | 2023.11.10 |
| LeetCode 1845. Seat Reservation Manager (0) | 2023.11.07 |
| LeetCode 1441. Build an Array With Stack Operations (0) | 2023.11.04 |
| LeetCode 2265. Count Nodes Equal to Average of Subtree (0) | 2023.11.02 |