CODEWITHSUNDEEP
javastringstringbuilderpalindrome
user12207727
user12207727

Reputation:

Longest Palindrome Edge Case due to String / StringBuilder Equality

This code doesn't work for the test case: aacabdkacaa, but it works for babad or cbbd. I wrote a print statement to debug and realized the code thinks that the strings aacakdbacaa and aacabdkacaa are equivalent for some reason. They clearly aren't, so what am I missing?

class Solution {
    public String longestPalindrome(String s) {
        String longPal = "";
        for(int i = 0; i < s.length(); i++) {
            for(int j = s.length()-1; j >= i; j--) {
                if(s.charAt(i) == s.charAt(j)) {
                    StringBuilder sb = new StringBuilder(s.substring(i, j+1));
                    if(sb.reverse().toString().equals(sb.toString()) 
                       && sb.toString().length() > longPal.length()) {
                        longPal = sb.toString();
                        System.out.println(sb.toString()+" equals "+sb.reverse().toString());
                    }
                    sb.setLength(0);
                }
            }
        }
        return longPal;
    }
}

Upvotes: 1

Views: 131

Answers (2)

Ma3x
Ma3x

Reputation: 6589

The code does not think that aacakdbacaa and aacabdkacaa are equal.

The first part of the condition in the if statement is this

sb.reverse().toString().equals(sb.toString())

So what the code (JVM) thinks is that this condition is true. Why is that? What hidden knowledge is behind this (because there is some)?

The hidden knowledge part (it is not really hidden, it is in the documentation) is that StringBuilder reverse method changes the state of the StringBuilder (almost all SB methods do). The reverse method also returns the StringBuilder instance itself (some other SB methods do as well).

So the call to sb.reverse() just reverses the contents of the StringBuilder instance and returns the instance itself (the same instance that is!). The instance hasn't changed, just its inner state has changed.

Then we call toString() on it, which returns the String representation of the current state (as expected).

Then we call equals on the returned String and we pass into equals sb.toString() as the value for the first parameter. But sb is the same instance as what was returned from sb.reverse() before. Its state hasn't changed in between, so we get the same String representation returned from the call to sb.toString().

That is why

sb.reverse().toString().equals(sb.toString())

is true.

We could write it a bit differently and still get the same result

String s1 = sb.reverse().toString() // sb state changed here when .reverse() was called
String s2 = sb.toString()
s1.equals(s2) // true

Or like this, which makes it quite obvious

sb.reverse() // sb state changed here
String s1 = sb.toString()
String s2 = sb.toString()
s1.equals(s2) // true

However, we get a different result, if we use this order

String s1 = sb.toString()
sb.reverse() // sb state changed here
String s2 = sb.toString()
s1.equals(s2) // now it depends, true if palindrome, false otherwise!

which is the same as

String s1 = sb.toString()
String s2 = sb.reverse().toString()
s1.equals(s2) // true if palindrome, false otherwise!

So this would be the correct check to check for a palindrome

sb.toString().equals(sb.reverse().toString())

Bonus: The practice to return the same instance from a method call is called Fluent interface.

Upvotes: 2

william0754
william0754

Reputation: 44

StringBuilder's reverse() method causes it's character sequence to be replaced by the reverse of the sequence, so sb.reverse().toString().equals(sb.toString()) always results true. declare another string String p = sb.toString() then use it to compare sb.reverse().toString().equals(p.toString()) may solve the problem.

Upvotes: 1

Related Questions