https://leetcode.com/problems/longest-palindrome/
난이도 : easy
주어진 문자열을 이용하여 가장큰 Palindrome 을 만들어라
해당 문제는 Palindrome 에 특성을 이용해서 풀어야하는 문제이다. 주어진 문제에서 알파벳만 들어온다고 가정 하였으니 a-z 까지 들어올 것이다.
1. 문자열이 길이가 짝수 인지 아닌지를 판단한다. -> 짝수이면 회문의 길이는 2의 배수이다.
하지만 aaabbbaa 와 같은 경우는 문자열의 길이가 짝수이지만 회문이 아니다. aabbbaa 로 하나를 제거 해야 한다.
2. 홀수일때는 전체길이에서 +1 을 해줘야한다.
회문 aabbbaa 는 총길이는 7 홀수이면서 회문을 만족한다.
3. 문자열의 원소를 map 자료형에 key 로 만들고 value 를 증가 하여 count 를 한다.
홀수가 하나라도 있으면 마지막에 + 1을 하여 간단하게 풀 수 있다.
시간복잡도는 O(N)
공간복잡도는 s.length 길이가 2000 임으로 최대 O(N) 알파벳은 26까지 있으니 O(26) 으로해야하나. 공간복잡도를 잡는 것에 대해서 다시좀 알아봐야겠다.
class Solution {
public:
int longestPalindrome(string s) {
map<char, int> m;
for(char c:s) {
int cand = m[c]++;
}
char hasOdd = 0;
int count = 0;
for(auto a:m) {
count += a.second / 2;
if(a.second & 1) {
hasOdd = 1;
}
}
int sol = count * 2 + hasOdd;
return sol;
}
};
42. Trapping Rain Water (0) | 2021.09.04 |
---|---|
1. Two Sum (0) | 2021.09.04 |
9. Palindrome Number (0) | 2021.09.04 |
17. Letter Combinations of a Phone Number (0) | 2021.09.04 |
49. Group Anagram (0) | 2021.09.04 |
댓글 영역