Longest palindromic substring implementation- how k-j-1 gets the length of the palindromic substring

Question

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}

How does this get me the length of the palindromic substring? For example, we take the word "racecar". How can k-j-1 get me the length? It will get me 6-0-1, which would be 5.

Answer 1

To me the code looks correct, although it is hard to tell without knowing the rest.

Why is it correct?

This method is probably a helper procedure of a method which tries to find the largest palindrome. So maxLen is only modified if the found (extended, largest) palindrome is longer than the one found so far. That's why we only modify maxLen in the if-statement and not in the while. But why is it k - j - 1 and not k - j + 1? It is because in the while j is decremented and k is incremented if the characters match. This means that after the loop k is one greater than the last matching character and j is one smaller. Taking this into account we get (k - 1) - (j + 1) + 1. This is your formula with the adjustments. If we simplify we get (k - 1) - (j + 1) + 1 = k - 1 - j - 1 + 1 = k - j - 1. Exactly what we see in the code.

Btw this is also the reason why lo is j + 1 and not just j.

The "racecar" example would have j = -1 and k = 7, so maxLen = 7 - (-1) - 1 = 7 + 1 - 1 = 7. Which is correct.