넘치게 채우기
[LeetCode] 1759. Count Number of Homogenous Substrings 본문
https://leetcode.com/problems/count-number-of-homogenous-substrings/description/
leetcode - Count Number of Homogenous Substrings
문제 유형: 투 포인터 / 슬라이딩 윈도우
문제 난이도: Medium
문제
Given a string s, return the number of homogenous substrings of s. Since the answer may be too large, return it modulo 10^9 + 7.
A string is homogenous if all the characters of the string are the same.
A substring is a contiguous sequence of characters within a string.
문자열 s가 주어진다. 균질의 부분 문자열의 개수를 반환하라.
값이 클 수 있으니, 10^9 + 7로 나눠라.
문자열의 글자가 모두 똑같을 때 균질하다고 할 수 있다.
부분 문자열은 문자열 안의 인접한 문자들의 일련의 배열이다.
풀이
문제의 핵심은 각 부분 문자열의 최대 길이를 구하는 것이다.
예를 들면, ccc가 있다고 해보자.
이러면 c의 개수는 3개가 추가되고,
cc의 개수는 2개가 추가되고,
ccc의 개수는 1개가 추가된다.
찾은 부분 문자열의 길이를 n이라고 했을 때, 1+2+...+n개를 누적시킬 수 있고, 즉, n(n+1)/2만큼 늘어난다.
처음부터 문자열을 순회하면서 부분 문자열단위로 나눠서, 값을 누적시키고, 1e9+7로 나누면 된다.
코드
C++
class Solution {
private:
const int MOD = 1e9+7;
public:
int countHomogenous(string s) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int idx = 0;
long long count = 0;
while (idx < s.size()) {
long streak = 1;
while (idx < s.size() - 1 && s[idx] == s[idx + 1]) {
streak++;
idx++;
}
count += (streak+1) * streak / 2;
idx++;
}
return count%MOD;
}
};
'PS > LeetCode' 카테고리의 다른 글
[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] 2849. Determine if a Cell Is Reachable at a Given Time (0) | 2023.11.08 |
LeetCode - 1921. Eliminate Maximum Number of Monsters (0) | 2023.11.07 |
[LeetCode] 1845. Seat Reservation Manager (0) | 2023.11.06 |