Code Roasting the Leetcode Submission
Let’s do some code-roasting, shall we? 😛 Today’s Leetcode challenge is straightforward: “Longest Palindrome.” The problem statement is simple: given a string consisting of lowercase and uppercase characters, return the longest palindrome length that can be built with the supplied letters.
This is a simple counting problem that can be solved by counting the appearance of the characters in the string. If a character appears as many as even times, that character pair can be used to construct a palindrome. If there is a remainder odd character that remains, we can take a single odd character to put in the middle of the palindrome string.
Let’s check out some solutions that were submitted on the Leetcode:
Solution 1: “One thing, I don’t know While.. (I tried so hard)”
Take a look at this solution that uses lots of while:
int longestPalindrome(char* s) {
int hash[124];
int a=0;
while(a!=124){
hash[a]=0;
a++;
}
a=0;
while(s[a]!='\0'){
hash[s[a]]++;
a++;
}
int odd=0;
int even=0;
a=0;
while(a!=124){
if(hash[a]%2==0){
even=even+hash[a];
}
else{
if(odd==0){
odd=hash[a];}
else{
odd= odd+hash[a]-1;}
}
a++;
}
return odd+even;
}
This solution uses an integer table with 124 rows to store the count of the characters. The first ick moment that we encounter is that it initializes the table with manual loop:
while(a!=124){
hash[a]=0; a++;
}
While actually, it can be just using a single statement memset(hash, 0, sizeof(hash));. From Godbolt, the resulting assembly for both manual loop and the memset are exactly the same. Writing your own while loop to initialize a memory block to a certain value does not provide an added benefit except increasing the chance of having a mistakes.
xorl %eax, %eax movl $62, %ecx leaq -120(%rsp), %rdx movq %rdx, %rdi rep stosq
The second while block performs iteration to count the number of characters. The row of the table is indexed by the character value. On each character, the loop increments the character count on the table. The last while loop iterates the counter table and checks for each element to compute the string length. If it is even, add directly the count to the length. If it is odd, reduce the count by one and add it to the length.
The second ick from this code is that this algorithm unnecessarily stores the even and odd counts separately. In the end, the odd and even are added together without serving any purpose to be counted separately in the first place. This creates confusing code, and the compiler is also typically unable to optimize this situation. In Godbolt, we can observe that the even and odd values are stored separately because the compiler cannot “simplify” computation that yields observable behavior.
In short, think simpler when writing code. Do not think too complex and overcomplicate your solution. So people won’t ask, “WHY…”
Solution 2: Similar to the previous one
Let’s check another solution:
int longestPalindrome(char *s) {
int freq[58] = {0};
int length = strlen(s);
for (int i = 0; i < length; i++) {
int letterIndex = 'z' - s[i];
freq[letterIndex]++;
}
bool odd_letter_taken = false;
int count = 0;
int longest = 0;
for (int i = 0; i < 58; i++) {
count = freq[i];
if (count >= 1) {
if (count % 2) {
if (odd_letter_taken) {
longest += count - 1;
} else {
longest += count;
odd_letter_taken = true;
}
} else {
longest += count;
}
}
}
return longest;
}
This solution’s thinking is exactly the same as the first solution’s. It just uses a different mechanism. It elegantly used the zero initializer for the counter table, which is an even better solution than my memset solution. It also uses fewer rows as we can assume we only need to store the character point between uppercase and lowercase A to Z, which is less than 124 characters.
However, this solution introduces another ick. It uses strlen to compute the length of the string for the iteration. This is extremely unnecessary because we know that the input string is null-terminated. So, we can always iterate every character until we reach the null character, which indicates the end of the string. strlen may be necessary if we want to use the string length for computation, such as for divide and conquer algorithm. For this matter, where the length is only used for iteration, using strlen is a bad choice.
Another problem is that this algorithm is too convoluted, with lots of branching with ifs. In secure programming, this kind of algorithm typically yields more observable side-channel behavior as it may perform jumps too often. If we check Godbolt, this algorithm yields 7 compare instructions with 9 jumps. The previous solution yields 6 compares with 6 jumps. The number of jumps corresponds to the number of basic blocks in the resulting assembly code. Reducing the number of basic blocks is always a good practice, which can be done by us as a programmer by not introducing too many unnecessary branching in our program.
Again, the caveat is: think simpler!
Solution 3: Constantly mad
Check this painful code:
#include <string.h>
#include <stdbool.h>
int longestPalindrome(char* s) {
if(strlen(s)==1)
{
return 1;
}
else
{
bool check1=false;
int counter=0;
int len=strlen(s);
if(len%2==0)
{
counter=0;
}
int arr[64];
for(int i=0;i<64;i++)
{
arr[i]=0;
}
for(int i=0;i<len;i++)
{
if((s[i]<='Z')||(s[i]>='A'))
{
arr[(int)s[i]-65]=arr[(int)s[i]-65]+1;
}
else if((s[i]<='z')||(s[i]>='a'))
{
arr[(int)s[i]-97+32]=arr[(int)s[i]-97+32]+1;
}
}
for(int i=0;i<64;i++)
{
if((check1==false)&&((arr[i]>=1)&&(arr[i]%2==1)))
{
counter=counter+1;
check1=true;
}
if(arr[i]>1)
{
counter+=(arr[i]/2 )*2;
}
}
return counter;
}
}
There are so many icks of this code. The first noticeable one is that it is using strlen TWICE. Although the compiler is smart enough to elide the second call to the strlen, this is because the compiler already has a presumption that strlen is a reentrant function that does not yield a side effect that can be observed by our code. If the compiler does not have such an assumption (e.g., calling strlen the second time with the same parameter returns a different result), the compiler will not eliminate the second call to the strlen.
The second ick is the counting loop. Check the condition in the if block:
if((s[i]<='Z')||(s[i]>='A'))
{
arr[(int)s[i]-65]=arr[(int)s[i]-65]+1;
}
else if((s[i]<='z')||(s[i]>='a'))
{
arr[(int)s[i]-97+32]=arr[(int)s[i]-97+32]+1;
}
It is totally WRONG. The if will ALWAYS be true because it is an OR condition. Literally it checks if the character is above or equal to A OR lower or equal to Z. It means it SATISFIES all characters. For God’s sake! The second branch is never evaluated at all, and the compiler eliminates the branch as it is a dead code. The reason why the code is still working and produces the correct result is because the program allocates enough array slots to cater to all possible ASCII characters, and technically, there are no differences between storing the count of lowercase and uppercase characters. The second If clause was already unnecessary from the beginning.
The second ick from this part of the code is that the expression that computes the index is put inside the array indexer directly. This makes this code HARD to read. It may also leads to more error as it duplicates the expression on the right-hand side of the assignment. You can just use += or even ++ operator in the first place!
Let’s not go to the last loop, which it is also poorly written. If I read this kind of code in a code review or programming assignment, I will refuse the merge request or give it a zero score for cleanliness.
Solution 4: Fancy Solution
After getting headache from nasty solution presented above, I found a very fancy solution:
int longestPalindrome(char* s) {
int m[128] = { 0 }, a = 0, b = 0, c;
while (*s && ++m[*s++]);
for (int i = 'A' - 1 ; ++i <= 'z' ; m[i] && (a += m[i] - ((b |= c = m[i] & 0x1), c)));
return a + b;
}
This is a very smart solution, although it is not directly obvious. Let’s breakdown the code. The way of thinking is exactly the same as the previous solutions, using a table to count the number of character appearances. It allocates 128 rows of tables and initializes it to zero using initialization syntax (which is good).
The first loop performs the counting for each character. How does it do the trick? It is by shortcircuit operation! The logical AND expression (&&) is a binary expression, which has the behavior as such that when the first operand is false, the second operand will not be evaluated as the result of the expression will be false regardless of the second operand. The condition expression in the while loop as follows: *s && ++m[*s++] ,where the first operand dereferences the pointer s. If the value of the character pointed by s is zero (a.k.a. null character), the second operand will not be evaluated, and the loop will stop.
If it is not a null character, the second operand will be executed in the order as follow:
- Dereference the pointer s and obtain the character value.
- Increment pointer s to the next character.
- Use the character value to index the table m.
- Increment the indexed value in table m.
The more interesting part is on the second for-loop:
for (int i = 'A' - 1 ; ++i <= 'z' ; m[i] && (a += m[i] - ((b |= c = m[i] & 0x1), c)));
Firstly, it only necessarily loops from character A to character z. It does not need to loop the entire table as other ASCII values outside of the alphabet range. That’s why it initializes the i value into 'A' - 1to get the index of character A. What is interesting is the third part (post-loop expression) of the for-loop: m[i] && (a += m[i] - ((b |= c = m[i] & 0x1), c)).This expression again exploits the behavior of the shortcircuiting of operator logical AND. It can be read simply as if the current character count is not zero, evaluate the second expression.
The second expression (a += m[i] - ((b |= c = m[i] & 0x1), c))adds the variable a with the current character count, minus one if the character count is odd value. But wait, how? Let’s follow the steps:
- Evaluate the expression
m[i] & 0x1that performs bitwise AND operator to the value with 1. The least-significant bit in a binary number indicates an odd value. - Assign the result of the value into c.
- Bitwise-OR the value in c into b. So, if b is still zero, it will become one. If it is already one, it stays one.
- The comma operator always produces the second operand. Since the second operand is c, return c to the higher expression chain, which is the subtraction with the current count.
This is a play of operator short-circuiting, precedence, and behavior of pre- and post-increment and comma operators. It is okay to use it in codes, but try to use it only on trivial things like this. It can obscure the semantics and potentially introduce bugs if used improperly. When in doubt, use regular line-by-line expressions.
Solution 5: Bad Leetcode Suggested Solution
Leetcode presented three “greedy” approach in their C++ solution, which all of them uses hash map or hash set from the standard library. This is extremely unnecessary and unreasonable. Why would you use a complex hashtable just to store a table with fixed size and known range. It adds unnecessary complexity of hashtable operation, such as collision checking, resizing, and so on. You don’t even need a complex data structure for that. You can check directly the proposed solution here. I would not say that this is a good solution. As interviewer, I would also question why the person decides to use hashtable.
My Solution
Most solutions are using more than one loop. The ideal solution only requires one loop, and a several variable to store the count. You don’t even need an array for that! The third solution from the proposed Leetcode solution already has a correct way of thinking, but the ick was it was unnecessarily using hash set. You only need a 64-bit size variable to store the information!
So the idea, is that the program loops for every character. If a character appears, check if it has appeared in processed character. If it has not appeared, remember that that character appears. If it has appeared before, it means we have a pair of character, add two to the length of the palindrome, and forget that we see that character. If at the end of the loop there is any character left, then add one length more to the palindrome length.
Keep it simple, stupid! Well, I am stupid enough so I coded my implementation in assembly language lol.
int longestPalindrome(char const* s);
__asm__(R"(
.global longestPalindrome
.type longestPalindrome, @function
longestPalindrome:
xor %rax, %rax
xor %rsi, %rsi
mov $2, %r8
loop:
cmpb $0, (%rdi)
jz exit
movb (%rdi), %cl
sub $65, %cl
mov $1, %rdx
shl %cl, %rdx
mov %rdx, %rcx
and %rsi, %rcx
cmovnz %r8, %rcx
add %rcx, %rax
xor %rdx, %rsi
inc %rdi
jmp loop
exit:
mov $1, %r8
xor %rcx, %rcx
test %rsi, %rsi
cmovnz %r8, %rcx
add %rcx, %rax
ret
)");
With this idea, you only need to store a single bit for every character. That single bit indicates that the character appearance is odd. Since we have at most 52 character (plus 6 character between ‘Z’ and ‘a’), we can simply store the all information in a 64-bit bitfield. To set and unset the bitfield, we simply build a mask by left-shifting the character index. The code above when written in C, it would be:
int longestPalindrome(char const* s)
{
int count = 0;
unsigned long long bitfield = 0;
while(*s)
{
uint64_t mask = 1ull << (*s - 'A');
if(bitfield & mask)
count += 2;
bitfield ^= mask;
s++;
}
return count + (bitfield ? 1 : 0);
}
If we pass above code to GCC, it will produce slightly similar code as my handwritten assembly. However, Clang does not use bitshift operation, instead opting to use Bit Test (BT) and Bit Test and Complement (BTC) instruction as it identifies that the bit shifting operation is simply to build a mask for bitwise operation. This shows that compiler is way smarter to perform rigorous optimization than human.
longestPalindrome(char const*): # @longestPalindrome(char const*)
movzbl (%rdi), %edx
testb %dl, %dl
je .LBB0_1
incq %rdi
xorl %ecx, %ecx
xorl %eax, %eax
.LBB0_3: # =>This Inner Loop Header: Depth=1
movl %eax, %esi
addb $-65, %dl
movzbl %dl, %edx
leal 2(%rsi), %eax
btq %rdx, %rcx
cmovael %esi, %eax
btcq %rdx, %rcx
movzbl (%rdi), %edx
incq %rdi
testb %dl, %dl
jne .LBB0_3
cmpq $1, %rcx
sbbl $-1, %eax
retq
.LBB0_1:
xorl %eax, %eax
retq
