DEV Community

loading...

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

Collapse
alisabaj profile image
Alisa Bajramovic Author

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).

Collapse
salyadav profile image
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 :)

Forem Open with the Forem app