[LeetCode] 1759. Count Number of Homogenous Substrings

https://leetcode.com/problems/count-number-of-homogenous-substrings/description/

Count Number of Homogenous Substrings - LeetCode

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;
    }
};