❔ LeetCode 409 Longest Palindrome
So I have a very hard time trying to understand the logic/thought process behind this puzzle. The full puzzle description is here
https://leetcode.com/problems/longest-palindrome/?envType=study-plan&id=level-1
I understand I need to care about the middle chars (like for example if the string is "abcccab" the middle chars to care about are "ccc"). But I am totally stuck with how to go about the rest. I have watched a couple of videos explaining "add +1 to the length of the odd string" which left me rolling eyes. I need to apply foreach/for loops, sure I got it but I am generally puzzled with how to apply pointers to this puzzle.
Could anyone kindly explain the basic logic for this LC exercise
(no code example please) to me like you would do it to a 5 y/o?
LeetCode
Longest Palindrome - LeetCode
Longest Palindrome - Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.
Letters are case sensitive, for example, "Aa" is not considered a palindrome here.
Example 1:
Input: s = "abccccdd"
Output: 7
Explanation: One longest palindrome that can...
11 Replies
Explaining the logic without explaining the underlying algorithm to solve the problem sounds kinda hard
Ok, then could you kindly explain the logic with the algorithm? I just don't want to glare the solution code just yet
Theres several different ways to solve it in varying complexity.
One way would be to use the "expand around center" algorithm. Loop through indexes in the string (0 to Length), and at each index, you expand in both directions until the string is no longer a pallendrome.
Given
bbaaabb
You'd skip index 0 because you can't expand left,
1. bba is not a pallendrome
2. baa is not
3 aaa is, expand out, baaab is, expand out, bbaaabb is, and you can't expand further.
4 aab is not
5 abb is not
6 skip because you can't expand rightthis isn't the problem
the problem is to give the length of the largest palindrome you can build using a given set of characters
your right I misread
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.Thank you so much (and sorry for the late response, I have been busy in the last few days). So if I want to give the length of the largest palindrome I can apply this expand around center algorithm. Let's say - would it be one of the possible workaround to check the length of the palindrome which I can't expand further (like cccbbbbbccc then I would say the length is 11)?
nah they were wrong about the question
that isn't the right algorithm
it's asking, if you're allowed to rearrange the letters, what's the length of the longest palindrome you can make
they thought the question was "what's the longest palindrome you can make from a substring of this string?"
which is a different question
Yeah I understand I need to find out the length of the longest palindrome I can make
I still feel like allergic to think about the cases where the length of the palindrome is odd or even
Maybe you can count the occurrences of each character, check if there is at least 1 character with an odd number of occurrences, then sum up the occurances / 2 * 2, and add 1 at the end if there was an odd number.
abccccdd has an odd number of a and b's,
a 1 / 2 * 2 = 0
b 1 / 2 * 2 = 0
cccc 4 / 2 * 2 = 4
dd 2 / 2 * 2 = 2
add one because at least 1 character had an odd number and you get 7 is the longest.Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.