Dec 10, 2024

2981. Find Longest Special Substring That Occurs Thrice I

내 코드

79ms, 29.90MB

class Solution {
public:
    int maximumLength(string s) {
        // 다 만들기
        int len = static_cast<int>(s.length()); // ~ 50
        unordered_map<string, int> m;
        int answer{-1};
        for(int i{};i<len;++i) {
            for(int j{i};j<len;++j) {
                string now = s.substr(i, j - i + 1); // (index, length)
                // single check..
                char last = now[0];
                bool chk{};
                for(int k{1}, e{static_cast<int>(now.length())}; k < e;++k) {
                    if(last != now[k]) {
                        chk = true;
                        break;
                    }
                }
                if(chk) continue; // not special

                if(m.count(now)) {
                    m[now]++;
                    if(m[now] >= 3) {
                        answer = max(answer, static_cast<int>(now.length()));
                    }
                }
                else {
                    m.emplace(now, 1);
                }
            }
        }

        return answer;
    }
};

Solution

Approach 1: Brute-Force Approach

22ms, 12.28MB
Complexity
- Let $n$ be the length of the string s.
- Time Complexity: $O(n^3)$
- Space Complexity: $O(n^2)$

class Solution {
public:
    int maximumLength(string s) {
        // Create a map of strings to store the count of all substrings.
        map<string, int> count;
        for (int start = 0; start < s.length(); start++) {
            string currString;
            for (int end = start; end < s.length(); end++) {
                // If the string is empty, or the current character is equal to
                // the previously added character, then add it to the map.
                // Otherwise, break the iteration.
                if (currString.empty() or currString.back() == s[end]) {
                    currString.push_back(s[end]);
                    count[currString]++;
                } else {
                    break;
                }
            }
        }

        // Create a variable ans to store the longest length of substring with
        // frequency atleast 3.
        int ans = 0;
        for (auto i : count) {
            string str = i.first;
            if (i.second >= 3 && str.length() > ans) ans = str.length();
        }
        if (ans == 0) return -1;
        return ans;
    }
};

GPT

아래 코드는 주어진 문자열 s에서 다음 조건을 만족하는 가장 긴 부분 문자열(substring)의 길이를 찾는 문제를 다룹니다.

문제 조건 추측:

부분 문자열이 “동일한 문자로만 이루어진” 연속된 문자열이어야 합니다.
그러한 부분 문자열이 3번 이상 등장해야 합니다(빈도 ≥ 3).
이 조건을 만족하는 부분 문자열 중 가장 긴 길이를 찾아내고, 없으면 -1을 반환합니다.

코드 동작 과정:

모든 가능한 부분 문자열 추출 (중첩 루프):

for (int start = 0; start < s.length(); start++) {
    string currString;
    for (int end = start; end < s.length(); end++) {
        // 만약 currString이 비어있거나, 현재 추가하는 문자(s[end])가 currString의 마지막 문자와 동일하다면 currString에 이어 붙인다.
        if (currString.empty() || currString.back() == s[end]) {
            currString.push_back(s[end]);
            count[currString]++;
        } else {
            // 만약 다르면, 더 이상 이 인덱스 start로 시작하는 동일 문자 반복 부분 문자열을 확장할 수 없으므로 break.
            break;
        }
    }
}

여기서 포인트는 if (currString.empty() or currString.back() == s[end]) 조건입니다. 즉, 현재 부분 문자열을 만들 때 currString이 비어있거나 지금까지 모은 부분 문자열의 마지막 문자와 s[end]가 같으면 이어 붙이는 방식으로 “하나의 문자가 반복된” 부분 문자열만 추출하고 있습니다.

이중 for문을 통해 모든 시작점 start에 대해 확장 가능한 최대한의 동일 문자 반복 부분 문자열을 추출하고, 그 문자열의 빈도수를 count 맵에 기록합니다.

부분 문자열 빈도 분석:
모든 가능한 동일 문자 반복 부분 문자열을 추출한 뒤, count 맵에는 각 부분 문자열이 등장한 횟수가 저장됩니다.
```
int ans = 0;
for (auto i : count) {
    string str = i.first;
    if (i.second >= 3 && (int)str.length() > ans) {
        ans = (int)str.length();
    }
}
```
여기서 i.second는 해당 부분 문자열의 빈도수, i.first는 해당 부분 문자열을 나타냅니다.
빈도수가 3 이상이며, 현재까지 확인한 부분 문자열 중 가장 긴 길이를 갱신합니다.
결과 반환:
```
if (ans == 0) return -1;
return ans;
```
만약 조건을 만족하는 부분 문자열을 찾지 못했다면 ans가 0일 것이므로 -1을 반환합니다.
그렇지 않다면 최대 길이를 반환합니다.

정리:

이 코드는 문자열 s 내에서 “한 문자로만 이루어진” 부분 문자열을 모두 찾아 빈도를 세고, 이 중 3번 이상 등장하는 가장 긴 문자열의 길이를 찾는 알고리즘입니다.
시간 복잡도는 상당히 클 수 있습니다(O(n²) 이상) 왜냐하면 거의 모든 시작점부터 가능한 부분 문자열을 만들고 count에 넣기 때문입니다.
조건에 맞는 부분 문자열이 없으면 -1을, 있으면 그 중 가장 긴 길이를 반환합니다.

Approach 2: Optimized Hashing

7ms, 10.91MB
Complexity
- Let $n$ be the length of the string s.
- Time Complexity: $O(n^2)$
- Space Complexity: $O(n^2)$

class Solution {
public:
    int maximumLength(string s) {
        // Create a map of strings to store the count of all substrings.
        map<pair<char, int>, int> count;
        int substringLength = 0;
        for (int start = 0; start < s.length(); start++) {
            char character = s[start];
            substringLength = 0;
            for (int end = start; end < s.length(); end++) {
                // If the string is empty, or the current character is equal to
                // the previously added character, then add it to the map.
                // Otherwise, break the iteration.
                if (character == s[end]) {
                    substringLength++;
                    count[{character, substringLength}]++;
                } else {
                    break;
                }
            }
        }

        // Create a variable ans to store the longest length of substring with
        // frequency atleast 3.
        int ans = 0;
        for (auto i : count) {
            int len = i.first.second;
            if (i.second >= 3 && len > ans) ans = len;
        }
        if (ans == 0) return -1;
        return ans;
    }
};

GPT

아래 코드는 문자열 s에서 “같은 문자가 연속해서 등장하는 부분 문자열”을 모두 찾아 그 빈도를 세고, 그 중 3회 이상 나타나는 가장 긴 부분 문자열의 길이를 찾는 방식으로 동작합니다.

코드 동작 과정:

부분 문자열 추출 방식 변경
이전 코드에서는 실제 부분 문자열(예: “aaa”) 자체를 key로 해서 map에 저장했지만, 이 코드는 (문자, 길이)의 쌍을 key로 사용합니다. 즉, 동일한 문자로만 이루어진 부분 문자열은 그 특징을 “어떤 문자로 구성되었는지”와 “부분 문자열의 길이”만으로 고유하게 표현할 수 있습니다.

예를 들어, “aaa”라는 부분 문자열은 ( ‘a’, 3 ) 라는 key로 표현할 수 있습니다.
count 맵 구조:
```
map<pair<char, int>, int> count;
```
이 맵의 key는 (character, substringLength)이고 value는 해당 (문자, 길이)의 부분 문자열이 몇 번 등장하는지 나타내는 정수 카운트입니다.
부분 문자열 계산 루프:
```
for (int start = 0; start < s.length(); start++) {
    char character = s[start];
    substringLength = 0;
    for (int end = start; end < s.length(); end++) {
        if (character == s[end]) {
            substringLength++;
            count[{character, substringLength}]++;
        } else {
            break;
        }
    }
}
```
여기서 start 인덱스부터 시작해서 end를 확장해가며 s[start]와 같은 문자가 연속으로 이어지는 최대 길이를 찾아내는 과정입니다.
- character = s[start] : 시작 위치의 문자
- substringLength = 0 으로 초기화한 뒤, end를 증가시키며 s[end]가 character와 같으면 substringLength를 1씩 증가
- 매번 (character, substringLength)에 해당하는 카운트를 증가시킴
- 한 번이라도 다른 문자가 나오면 break 하여 다음 start 위치로 넘어갑니다.
예를 들어 s = "aaabb"라면:
- start = 0: s[0] = 'a'
  - end = 0: “a” 길이 1 → count[(‘a’,1)]++,
  - end = 1: “aa” 길이 2 → count[(‘a’,2)]++,
  - end = 2: “aaa” 길이 3 → count[(‘a’,3)]++,
  - end = 3: 문자 ‘b’ 나옴, break.
- start = 1: s[1] = 'a'
  - end = 1: “a” 길이 1 → count[(‘a’,1)]++
  - end = 2: “aa” 길이 2 → count[(‘a’,2)]++
  - end = 3: ‘b’ 등장, break.
- start = 2: s[2] = 'a'
  - end = 2: “a” 길이 1 → count[(‘a’,1)]++
  - end = 3: ‘b’, break.
- start = 3: s[3] = 'b'
  - end = 3: “b” 길이 1 → count[(‘b’,1)]++
  - end = 4: “bb” 길이 2 → count[(‘b’,2)]++
- start = 4: s[4] = 'b'
  - end = 4: “b” 길이 1 → count[(‘b’,1)]++
이렇게 반복하면 모든 “같은 문자 연속 부분 문자열”에 대한 빈도수가 map에 기록됩니다.
빈도수를 통한 결과 도출:
```
int ans = 0;
for (auto i : count) {
    int len = i.first.second;   // 부분 문자열 길이
    int frequency = i.second;   // 해당 길이 부분 문자열 빈도
    if (frequency >= 3 && len > ans) ans = len;
}
if (ans == 0) return -1;
return ans;
```
- count 맵을 순회하면서 빈도(frequency)가 3 이상인 (character, length) 쌍 중 가장 긴 length를 찾습니다.
- 만약 그런 부분 문자열이 하나도 없다면 ans는 0일 것이므로 -1을 반환합니다.
- 그렇지 않다면 최대 길이 ans를 반환합니다.

정리:

이 코드는 문자열 내에서 “동일한 문자로 이루어진 부분 문자열”을 모두 탐색하고, (문자, 부분 문자열 길이)를 통해 해당 패턴이 몇 번 등장했는지 센 뒤, 세 번 이상 등장하는 가장 긴 부분 문자열의 길이를 찾는 방식입니다.
시간 복잡도는 O(n²)에 가깝지만, 문제 크기에 따라 사용할 수 있는 단순한 방법입니다.
조건을 만족하는 부분 문자열이 없으면 -1을, 있으면 그 중 가장 긴 길이를 반환합니다.