[LeetCode] 2981. Find Longest Special Substring That Occurs Thrice I

https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-i/description/

leetcode - Find Longest Special Substring That Occurs Thrice I

문제 유형: 문자열 처리, 슬라이딩 윈도우

문제 난이도: Medium

 

문제

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

 

영어 소문자로만 이루어진 문자열 s를 받는다.

문자열의 모든 글자가 한 글자로만 되어있으면 특별하다고 한다.

예를 들어서, "abc"는 특별하지 않지만, "ddd"는 특별하다.

적어도 세 번 이상 나오는 특별한 부분문자열의 가장 긴 길이를 구하시오. 없으면 -1을 반환하시오.

 

풀이

"aaaa"가 있다고 해보자.

"a"는 4개, "aa"는 3개, "aaa"는 2개, "aaaa"는 1개의 카운트가 세진다.

 

즉, 문자열 s를 슬라이딩 윈도우로 순회하면서 개수를 누적해주면 된다.

cnt[ch][len] = ch글자로만 이루어진 len길이의 출현 수로 저장하면 된다.

 

값이 3 이상인 가장 큰 len을 반환하자.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int maximumLength(string s) {
        int n = s.size();
        int maxLen = -1;
        vector<vector<int>> cnt(26, vector<int>(51, 0));

        int l = 0;
        int r = 0;
        while(l < n) {
            while(r < n && s[l] == s[r]) {
                r++;
            }
            for(int i = 1; i <= r-l; ++i) {
                cnt[s[l] - 'a'][i] += (r-l) - i + 1;
            }
            l = r;
        }

        for(const auto &ch : cnt) {
            for(int i = 1; i <= 50; ++i) {
                if(ch[i] >= 3) maxLen = max(maxLen, i);
            }
        }

        return maxLen;
    }
};