Let's make this one less mysterious. For 409. Longest Palindrome, the solution in this repository is mainly a two pointers solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, greedy.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are longestPalindrome.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N)O(N), where NN is the length of s. We need to count each letter.
- Space: O(1)O(1), the space for our count, as the alphabet size of s is fixed. We should also consider that in a bit complexity model, technically we need O(\log N)O(logN) bits to store the count values.
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
03
04This is case sensitive, for example "Aa" is not considered a palindrome here.
05
06Note:
07Assume the length of given string will not exceed 1,010.
08
09Example:
10
11Input:
12"abccccdd"
13
14Output:
157
16
17Explanation:
18One longest palindrome that can be built is "dccaccd", whose length is 7.
19**/
20
21//Runtime: 8 ms, faster than 80.68% of C++ online submissions for Longest Palindrome.
22//Memory Usage: 8.9 MB, less than 100.00% of C++ online submissions for Longest Palindrome.
23
24/**
25Approach #1: Greedy [Accepted]
26Intuition
27
28A palindrome consists of letters with equal partners, plus possibly a unique center (without a partner). The letter i from the left has its partner i from the right. For example in 'abcba', 'aa' and 'bb' are partners, and 'c' is a unique center.
29
30Imagine we built our palindrome. It consists of as many partnered letters as possible, plus a unique center if possible. This motivates a greedy approach.
31
32Algorithm
33
34For each letter, say it occurs v times. We know we have v // 2 * 2 letters that can be partnered for sure. For example, if we have 'aaaaa', then we could have 'aaaa' partnered, which is 5 // 2 * 2 = 4 letters partnered.
35
36At the end, if there was any v % 2 == 1, then that letter could have been a unique center. Otherwise, every letter was partnered. To perform this check, we will check for v % 2 == 1 and ans % 2 == 0, the latter meaning we haven't yet added a unique center to the answer.
37**/
38
39/**
40Complexity Analysis
41
42Time Complexity: O(N)O(N), where NN is the length of s. We need to count each letter.
43
44Space Complexity: O(1)O(1), the space for our count, as the alphabet size of s is fixed. We should also consider that in a bit complexity model, technically we need O(\log N)O(logN) bits to store the count values.
45**/
46
47//Runtime: 8 ms, faster than 80.68% of C++ online submissions for Longest Palindrome.
48//Memory Usage: 8.9 MB, less than 100.00% of C++ online submissions for Longest Palindrome.
49
50class Solution {
51public:
52 int longestPalindrome(string s) {
53 map<char, int> count;
54
55 for(char c : s){
56 if(count.find(c) == count.end()){
57 count[c] = 1;
58 }else{
59 count[c]++;
60 }
61 }
62
63 int ans = 0, maxOdd = 0;
64 for(map<char, int>::iterator it = count.begin(); it!= count.end(); it++){
65 ans += it->second/2*2;
66 if(ans%2 == 0 && it->second%2 == 1){
67 ans++;
68 }
69 }
70 return ans+maxOdd;
71 }
72};Cost
Complexity
Time
O(N)O(N), where NN is the length of s. We need to count each letter.
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(1)O(1), the space for our count, as the alphabet size of s is fixed. We should also consider that in a bit complexity model, technically we need O(\log N)O(logN) bits to store the count values.
Auxiliary state plus the answer structure where the problem requires one.