Discussion on: The Longest Palindromic Substring: Solving the Problem Using Constant Space

[Saloni Yadav]

Hi. A really a nice approach! I was wondering about the time complexity. I sometimes find it difficult to determine the time complexity of an algo with certainty, even the ones i write. Could you please elaborate on that... I wrote a different algorithm, just trying to judge if this one has a better complexity than mine, because mine does not eally perform that efficiently:

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let len = s.length;
    while (len>0) {
        for (let i=0; i<s.length-len+1; i++) {
            let str = s.slice(i, i+len);
            if (isPalindrom(str))
                return str;
        }
        len--;
    }
    return "";
};

const isPalindrom = function(arr) {
    let i=0;
    let j=arr.length-1;
    while (i<=j) {
        if (arr[i]!==arr[j])
            return false;
        i++; j--;
    }
    return true;
}

[Alisa Bajramovic]

Hi Saloni,
In the algorithm I used above, the reason its time complexity is O(n^2) can be found by looking at the for loop. The for loop examines each element of s, which takes O(n) time (n being the length of s). Then, inside the for loop, I call expandAroundCenter. In expandAroundCenter, I'm again traversing the string (even though I may just be looking at one character, I could be looking at the entire string again, like in the case of checking the "B" in "ABA"). That would take, at most, O(n) time. Because expandAroundCenter is nested inside the for loop, that means it takes a total of O(n^2) time.

In your function, you have a while loop, which goes from the end of the string to the start. In other words, you could write while (len>0) {... as for (let i = len; i > 0; i--) {. So in that line, that's O(n). Then inside the loop, you have another for loop. If you think about the example of "AAAA", the first time through the while loop, len would = 4, and inside the for loop, str would = "AAAA". Then, isPalindrom would be called, and it'd start at either end, and end up checking every character of the string, which is also O(n). So, it looks like overall the time would be O(n^2).

[Saloni Yadav]

Thank you for the help with time complexity Alisa! Also, your post is very well explained. So thank you for that as well :)