AI 요약관련 정보

• 주어진 문자열에서 길이가 3인 고유한 회문 부분수열의 개수를 찾는 문제로, 회문은 X_X 형태이며 가운데 문자는 중요하지 않음. 🧩
• 무차별 대입(N^3) 및 중간 최적화(N^2) 방식보다 효율적인 선형 시간(O(N)) 솔루션이 제시됨. 🚀
• 핵심 아이디어는 mid 포인터를 이동시키면서 left_set (왼쪽 고유 문자)과 right_map (오른쪽 문자 빈도수)을 관리하는 것. 💡
• right_map은 collections.Counter로 초기화하여 전체 문자열의 문자 빈도수를 저장하고, mid 문자가 지나갈 때마다 해당 문자의 카운트를 감소시킴. 📉
• left_set은 mid 포인터 왼쪽에 나타난 고유 문자들을 저장하며, mid 문자가 지나간 후 left_set에 추가됨. ➕
• 각 mid 문자 위치에서 left_set의 모든 문자에 대해 right_map에 해당 문자가 남아있는지 확인하여 회문 (바깥 문자, 중간 문자) 쌍을 result_set에 추가. 🎯
• result_set은 고유한 회문 쌍만 저장하는 해시셋으로, 최종적으로 이 해시셋의 크기가 정답이 됨. 🔢
• 이 접근 방식은 시간 복잡도 O(N) (알파벳 크기 26은 상수 취급) 및 공간 복잡도 O(1) (알파벳 크기에 비례)를 달성함. ⏱️