## DEV Community is a community of 638,993 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading...

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

## Replies for: 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 ... 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).