1930. Unique Length-3 Palindromic Subsequences

문제 링크


내 코드

해설 참고.


Solution

Approach 1: Count Letters In-Between

  • 176ms, 15.95MB
  • Complexity
    • Given nn as the length of ss.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        unordered_set<char> letters;
        for (char c : s) {
            letters.insert(c);
        }
        
        int ans = 0;
        for (char letter : letters) {
            int i = -1;
            int j = 0;
            
            for (int k = 0; k < s.size(); k++) {
                if (s[k] == letter) {
                    if (i == -1) {
                        i = k;
                    }
                    
                    j = k;
                }
            }
            
            unordered_set<char> between;
            for (int k = i + 1; k < j; k++) {
                between.insert(s[k]);
            }
            
            ans += between.size();
        }
        
        return ans;
    }
};

GPT

이 코드는 길이가 3인 회문(팰린드롬) 부분 수열의 개수를 찾는 문제를 해결합니다.
즉, 형태가 x _ x인 부분 수열(x는 같은 문자, _는 아무 문자 가능)의 개수를 구하는 문제입니다.

🔍 코드 개요

  1. 문자 집합(unordered_set)을 사용하여 중복 문자 제거
    • 문자열 s에서 고유한 문자만 고려.
  2. 각 문자의 첫 번째(i)와 마지막(j) 등장 위치를 찾음
  3. i와 j 사이의 서로 다른 문자 개수를 세어 카운트
    • 각 중간 문자가 x _ x 형태를 만들 수 있음
  4. 각 문자에 대해 between.size()를 더함
    • between.size()는 i와 j 사이에 있는 서로 다른 문자 개수

✅ 시간 복잡도: O(26 * n) = O(n) (최대 26개의 문자만 고려)
✅ 공간 복잡도: O(26) = O(1) (알파벳 소문자만 저장)

📌 코드 분석

1️⃣ 고유 문자 집합 생성

unordered_set<char> letters;
for (char c : s) {
    letters.insert(c);
}
  • unordered_set을 사용하여 s에서 중복 제거된 문자 집합 letters를 생성.
  • 최대 26개 문자만 저장하므로 O(1) 공간 사용.

2️⃣ 각 문자별로 첫 번째(i)와 마지막(j) 위치 찾기

for (char letter : letters) {
    int i = -1, j = 0;
    
    for (int k = 0; k < s.size(); k++) {
        if (s[k] == letter) {
            if (i == -1) { // 첫 번째 등장 위치
                i = k;
            }
            j = k; // 마지막 등장 위치
        }
    }
  • i: letter의 첫 번째 등장 위치
  • j: letter의 마지막 등장 위치
  • i == -1인 경우, 첫 번째 등장한 위치를 저장
  • 이후 같은 문자가 나오면 j를 업데이트하여 마지막 등장 위치를 저장

3️⃣ i와 j 사이의 서로 다른 문자 개수 찾기

unordered_set<char> between;
for (int k = i + 1; k < j; k++) {
    between.insert(s[k]);
}
  • i와 j 사이의 문자를 unordered_set에 추가
  • 각 중간 문자마다 x _ x 형태의 회문을 만들 수 있음

✅ 시간 복잡도 O(n) → 전체 O(26 * n) = O(n)
✅ 공간 복잡도 O(26) = O(1) (최대 26개 문자 저장)

4️⃣ 가능한 회문 개수 누적

ans += between.size();
  • between.size()는 현재 문자(letter)를 기준으로 만들 수 있는 x _ x 형태의 회문 개수.

5️⃣ 최종 결과 반환

return ans;

✅ 모든 문자에 대해 계산된 개수를 반환.

📌 예제 실행

string s = "aabca";
Solution sol;
cout << sol.countPalindromicSubsequence(s);

Step 1: 고유 문자 찾기

s = "aabca"
✅ letters = {'a', 'b', 'c'}

Step 2: 각 문자별로 i, j 찾기 & 중간 문자 개수 계산

(1) 문자 ‘a’

  • i = 0, j = 4
  • 중간 문자: "abc" ✅ between.size() = 3

(2) 문자 ‘b’

  • i = 1, j = 1
  • 중간 문자: 없음 ✅ between.size() = 0

(3) 문자 ‘c’

  • i = 3, j = 3
  • 중간 문자: 없음 ✅ between.size() = 0

최종 결과

ans = 3 + 0 + 0 = 3

✅ 출력: 3

⏱ 시간 복잡도 분석

연산시간 복잡도
고유 문자 찾기O(n)
각 문자별 i, j 찾기O(n)
중간 문자 개수 찾기O(n)
전체 시간 복잡도O(26∗n)=O(n)O(26 * n) = O(n)

✅ 최대 26개의 문자만 고려하므로 O(n) 에 해결 가능!
✅ 공간 복잡도 O(1) (문자 26개만 저장)

💡 최적화 가능?

✅ 더 빠르게 할 수 있는 방법

left[]와 right[] 배열을 사용하여 i, j를 빠르게 찾기!

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<int> first(26, -1), last(26, -1);
        for (int i = 0; i < s.size(); i++) {
            int idx = s[i] - 'a';
            if (first[idx] == -1) first[idx] = i;
            last[idx] = i;
        }

        int ans = 0;
        for (int c = 0; c < 26; c++) {
            if (first[c] == -1 || first[c] == last[c]) continue;

            unordered_set<char> between;
            for (int i = first[c] + 1; i < last[c]; i++) {
                between.insert(s[i]);
            }
            ans += between.size();
        }

        return ans;
    }
};

✅ first[c]와 last[c]를 미리 계산 → O(n)
✅ unordered_set을 사용해 중간 문자 찾기 → O(n)
✅ 최종 시간 복잡도 = O(n) 🚀

✅ 결론

✔ 길이 3의 회문 부분 수열(x _ x) 개수를 효율적으로 찾음
✔ O(n)으로 최적화된 풀이 사용 가능 🚀
✔ 문자열 문제에서 unordered_set과 prefix/suffix index 활용법 익힐 수 있음 🎯


Approach 2: Pre-Compute First and Last Indices

  • 146ms, 15.83MB
  • Complexity
    • Given nn as the length of ss.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<int> first = vector(26, -1);
        vector<int> last = vector(26, -1);
        
        for (int i = 0; i < s.size(); i++) {
            int curr = s[i] - 'a';
            if (first[curr] == - 1) {
                first[curr] = i;
            }
            
            last[curr] = i;
        }
        
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (first[i] == -1) {
                continue;
            }
            
            unordered_set<char> between;
            for (int j = first[i] + 1; j < last[i]; j++) {
                between.insert(s[j]);
            }
            
            ans += between.size();
        }
        
        return ans;
    }
};

GPT

이 코드는 길이가 3인 회문(팰린드롬) 부분 수열의 개수를 찾는 문제를 효율적으로 해결하는 O(n) 최적화 코드입니다.
즉, 형태가 x _ x인 부분 수열(x는 같은 문자, _는 아무 문자 가능)의 개수를 구하는 문제입니다.

🔍 코드 개요

  1. 각 알파벳(a~z)의 첫 등장 위치(first[])와 마지막 등장 위치(last[]) 저장
  2. 각 문자(x)를 기준으로 x _ x 형태의 중간 문자를 unordered_set을 이용해 카운트
  3. 모든 문자에 대해 가능한 x _ x 형태의 개수를 합산하여 반환

✅ O(n) 시간, O(1) 공간 (고정된 26개 문자만 저장)
✅ 빠르고 최적화된 방식 🚀

📌 코드 분석

1️⃣ first[]와 last[] 배열 초기화

vector<int> first(26, -1);
vector<int> last(26, -1);
  • first[i]: 문자 i(a부터 z)의 첫 번째 등장 인덱스
  • last[i]: 문자 i의 마지막 등장 인덱스
  • 처음에는 -1로 초기화 (아직 등장하지 않음)

2️⃣ first[]와 last[] 채우기

for (int i = 0; i < s.size(); i++) {
    int curr = s[i] - 'a';  // 문자 → 인덱스 변환
    if (first[curr] == -1) { 
        first[curr] = i; // 첫 등장 기록
    }
    last[curr] = i; // 마지막 등장 위치 계속 갱신
}

✅ O(n) 만에 문자열을 한 번만 순회하여 first[]와 last[] 계산
✅ 배열 접근 O(1) → 빠른 수행 가능

3️⃣ 각 문자별 x _ x 개수 계산

int ans = 0;
for (int i = 0; i < 26; i++) {  // a~z 순회
    if (first[i] == -1) continue; // 해당 문자가 존재하지 않으면 스킵

    unordered_set<char> between;
    for (int j = first[i] + 1; j < last[i]; j++) {
        between.insert(s[j]); // 중간 문자 추가
    }

    ans += between.size(); // 가능한 회문의 개수 추가
}
  • first[i] + 1부터 last[i] - 1까지 중간 문자 수집
  • 중복 제거를 위해 unordered_set 사용
  • between.size()를 ans에 더함

✅ 각 문자에 대해 O(n) 반복 → 총 O(26 * n) = O(n)

4️⃣ 최종 결과 반환

return ans;

✅ 가능한 x _ x 개수를 반환

📌 예제 실행

string s = "aabca";
Solution sol;
cout << sol.countPalindromicSubsequence(s);

Step 1: first[], last[] 계산

s = "aabca"

문자첫 등장 first[i]마지막 등장 last[i]
’a’04
’b’11
’c’33

✅ first = [0, 1, 3, -1, -1, ...]
✅ last = [4, 1, 3, -1, -1, ...]

Step 2: 가능한 x _ x 개수 계산

(1) 문자 ‘a’

  • i = 0, j = 4
  • 중간 문자: "abc" ✅ between.size() = 3

(2) 문자 ‘b’

  • i = 1, j = 1
  • 중간 문자: 없음 ✅ between.size() = 0

(3) 문자 ‘c’

  • i = 3, j = 3
  • 중간 문자: 없음 ✅ between.size() = 0

최종 결과

ans = 3 + 0 + 0 = 3

✅ 출력: 3

⏱ 시간 복잡도 분석

연산시간 복잡도
first[], last[] 계산O(n)
각 문자(a~z) 중간 문자 찾기O(n)
전체 시간 복잡도O(n)

✅ 최대 26개의 문자만 고려하므로 O(n) 에 해결 가능!
✅ 공간 복잡도 O(1) (고정된 26개 배열만 사용)

💡 개선 및 최적화

✅ unordered_set 대신 bitset을 사용하면 더 빠르게 가능!

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        vector<int> first(26, -1), last(26, -1);
        for (int i = 0; i < s.size(); i++) {
            int idx = s[i] - 'a';
            if (first[idx] == -1) first[idx] = i;
            last[idx] = i;
        }

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (first[i] == -1) continue;

            bitset<26> between;
            for (int j = first[i] + 1; j < last[i]; j++) {
                between.set(s[j] - 'a');
            }
            ans += between.count();
        }

        return ans;
    }
};

🚀 최적화된 코드의 장점

✅ unordered_set 대신 bitset<26>을 사용하여 메모리 절약 & 더 빠른 실행
✅ O(1) 공간, O(n) 실행 시간 유지
✅ bitset.count()는 O(1) 연산이라 unordered_set보다 빠름

✅ 결론

✔ O(n) 최적화된 알고리즘! 🚀
✔ 누적 인덱스(first, last)를 이용해 빠르게 해결
✔ unordered_set 대신 bitset을 사용하면 더 빠름
✔ 회문 문제에서 prefix/suffix index 활용법 익힐 수 있음 🎯