I learned that Manacher's algorithm could solve the problem with O(n). Here is the link with code from Wikipedia: https://en.wikipedia.org/wiki/Longest_palindromic_substring#Implementation
I'm confused about how to calculate the time complexity of the algorithm. Because it has two loops, the first is used to loop each item in the array, the second is used to expand around the center for each item, so my first guess is O(n^2). Somebody says that the total steps of the second loop is n, if this is true, then the time complexity is definitely O(n), but why is the total steps of the second loop is n?
Any help appreciated.