상세 컨텐츠

본문 제목

409. Longest Palindrome

Developer/LEETCODE

by cepiloth 2021. 9. 4. 11:29

본문

728x90
반응형

https://leetcode.com/problems/longest-palindrome/

 

Longest Palindrome - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

난이도 : 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;
    }
};
728x90
반응형

'Developer > LEETCODE' 카테고리의 다른 글

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

관련글 더보기

댓글 영역