넘치게 채우기
[LeetCode] 1930. Unique Length-3 Palindromic Subsequences 본문
[LeetCode] 1930. Unique Length-3 Palindromic Subsequences
riveroverflow 2023. 11. 14. 13:47https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/
Unique Length-3 Palindromic Subsequences - LeetCode
Can you solve this real interview question? Unique Length-3 Palindromic Subsequences - Given a string s, return the number of unique palindromes of length three that are a subsequence of s. Note that even if there are multiple ways to obtain the same subse
leetcode.com
leetcode - Unique Length-3 Palindromic Subsequences
문제 유형 : 문자열 처리 / 집합 / 투 포인터
문제 난이도 : Medium
문제
Given a string s, return the number of unique palindromes of length three that are a subsequence of s.
Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.
A palindrome is a string that reads the same forwards and backwards.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
- For example, "ace" is a subsequence of "abcde".
문자열 s가 주어진다. 이 안에서 길이가 3인 팰린드롬의 부분열을 구하시오.
중복은 있어도 하나로 간주됩니다.
팰린드롬은 뒤집어도 같은 걸 말합니다.
부분열은 기존 문자열에서 순서를 그대로 사용한 새로 만들어진 문자열이어야 합니다.
예를 들어 "ace"는 "abcde"에서 만들 수 있습니다.
풀이
길이가 3인 팰린드롬은 (문자)*(문자)의 형태를 가진다.
여기서 중복을 안센다면, 각 문자별로 가장 양 끝의 범위의 사이에 있는 문자들의 집합의 크기를 누적시키면 구할 수 있다.
코드
C++
class Solution {
public:
int countPalindromicSubsequence(string s) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int count = 0;
vector<int> firstIdx(26, INT_MAX);
vector<int> lastIdx(26);
for(int i = 0; i < s.size(); i++) {
firstIdx[s[i] - 'a'] = min(firstIdx[s[i] - 'a'], i);
lastIdx[s[i] - 'a'] = i;
}
for(int i = 0; i < 26; i++) {
if(firstIdx[i] < lastIdx[i]) {
count += set<char>(begin(s) + firstIdx[i] + 1, begin(s) + lastIdx[i]).size();
}
}
return count;
}
};
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 1980. Find Unique Binary String (0) | 2023.11.16 |
---|---|
[LeetCode] 1846. Maximum Element After Decreasing and Rearranging (0) | 2023.11.15 |
[LeetCode] 2785. Sort Vowels in a String (0) | 2023.11.13 |
[LeetCode] - 815. Bus Routes (0) | 2023.11.12 |
[LeetCode] 2642. Design Graph With Shortest Path Calculator (0) | 2023.11.11 |