loading...
Cover image for The Longest Palindromic Substring: Solving the Problem Using Constant Space

The Longest Palindromic Substring: Solving the Problem Using Constant Space

alisabaj profile image Alisa Bajramovic ・14 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Today's algorithm of the day is the Longest Palindromic Substring:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

For example, let's say you were given the string "prefer". The output of the function should be "refer", because that is the longest substring of "prefer" which is a palindrome.

A palindrome is a word that is the same forwards and backwards--for example, "kayak", "level", and "noon". A substring is a continuous series of characters in a string--for example, "flow" is a substring of "flower". This problem is asking you to find the longest substring which is a palindrome in a given string.

Like most algorithms, there's many ways to solve this problem, but today I'll be solving it using the "expand around the center" method. The advantage of this method is that it uses constant space (O(1)). Although it uses O(n^2) time, the very little space it takes up is really interesting to me, so I wanted to give this approach a try.

I'll start by going over the approach behind this problem. Then I'll go on to code the solution in JavaScript. Finally, I'll illustrate how it works with an example.

Expanding Around the Center: Approaching the Problem

Let's say you're given the string "watt". To find the longest palindromic substring, you'd want to check all of the points in the string and see if the left and right of that point are identical. We can call all of those points "centers". You may think there are 4 centers in "watt", because it's 4 characters long--however, there are actually 7 centers in "watt", or 2n - 1 centers in a string of length n.

The reason why this is the case is that the space between each letter is also a "center"--that is, a substring may have an even number of characters, and so there is no single "middle" letter.

In the example of "watt", the longest substring is "tt", which means its center is the space between "t" and "t".

The string "WATT" in bold letters. There are seven vertical red lines, one in the middle of each letter, and one between each letter.

So in the expanding around the center approach, we'll iterate through each character in the given string, and will check not only the substring that has a center at each character, but also the substring that has a center between any two characters.

Solving for the Longest Palindromic Substring

To start solving this problem, we can account for edge cases. If the given string is less than a character long, we can simply return an empty string--there's no "substring" of an empty string.

function longestPalindrome(s) {
  if (s.length < 1) return "";
  //...
}

Now, we'll want to keep track of where the longest palindromic substring starts, and how long it is. We want to do this so that we can return that section of the inputted string at the end. We can set both of those values equal to 0 to start. We also can include a return statement at the bottom of the function to return the maximum substring. When called on a string, the method .substr() returns the the substring of a string. The first parameter passed in is the starting index of the substring you want to return, and the second (optional) parameter is the number of characters you want to return. Therefore, we can return the substring that starts at maxSubStart and is maxSubLength characters long.

function longestPalindrome(s) {
  if (s.length < 1) return "";
  let maxSubStart = 0;
  let maxSubLength = 0;
  //...
  return s.substr(maxSubStart, maxSubLength);
}

Now, we'll want to walk through each character in s and perform checks on the substring at each step, so this is a good time to use a for-loop.

At each character in s, we'll want to check the substring which has a center at that character, and the substring which has a center between that character and the following character. We will write a helper function, expandAroundCenter to do this. expandAroundCenter will take in the string, the left parameter, and the right parameter. So, inside the for loop, we can call expandAroundCenter twice: once where left and right both equal the character we're currently on, and once where left equals the character we're currently on and right equals the next character in s.

function longestPalindrome(s) {
  if (s.length < 1) return "";
  let maxSubStart = 0;
  let maxSubLength = 0;
  for (let i = 0; i < s.length; i++) {
    const lengthCenteredAtChar = expandAroundCenter(s, i, i);
    const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
    //...
  }
  return s.substr(maxSubStart, maxSubLength);
}

We'll get back to writing the helper function in a minute. For now, we can continue writing the function we're on. expandAroundCenter will return lengths, and we want to know which one is longer: the substring that's centered at the character, or the substring that's centered at the space. So, we can use Math.max() and pass in both of those lengths. Whichever one is longer, we can set equal to a variable, longestSubAtChar, which is the longest substring at each character.

Then, we'll want to see if the longest substring at the character we're on is longer than the maximum substring we've seen so far. To check this, we can write a conditional statement inside the for loop.

function longestPalindrome(s) {
  if (s.length < 1) return "";
  let maxSubStart = 0;
  let maxSubLength = 0;
  for (let i = 0; i < s.length; i++) {
    const lengthCenteredAtChar = expandAroundCenter(s, i, i);
    const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
    const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
    if (longestSubAtChar > maxSubLength) {
      //...
    }
  }
  return s.substr(maxSubStart, maxSubLength);
}

If the current substring is longer than the maximum substring seen so far, we'll want to make the current substring the maximum. We'll do this by setting maxSubLength equal to longestSubAtChar.

We'll also want to change the starting point of the maximum substring so that we can return the correct substring at the end of the function. We can find the starting point by finding the halfway point of longestSubAtChar, and subtracting that from the character we're on.

In the example of "lava", the maximum substring is "ava", the center is "v" (index 2), and the start of that substring is "a" (index 1). In the example of "wattage", the maximum substring is "atta", the center is between "t" and "t" (index 2 and 3), and the start of that substring is "a" (index 1).

First is the string "LAVA", with the index values 0, 1, 2, 3 above each letter. There is a vertical red line going through the "V", and a blue horizontal line beneath the letters "AVA". Then there is the string "WATTAGE", with the index values 0, 1, 2, 3, 4, 5, 6 above each letter. There is a vertical red line going between "T" and "T", and a blue horizontal line beneath the letters "ATTA".

Finding half of the length of the substring means taking the length and subtracting 1, dividing that by 2, and performing Math.floor() on that calculation. Then, to find the start of the substring, subtract that number from i. (Note: you can see why you need to subtract 1 by looking at the example of "wattage". If we just divided 4 (the maxSubLength) by 2, we'd get 2. 2 (i) minus 2 is 0. The substring starts at 1, not 0. Subtracting one accounts for substrings of even lengths.)

function longestPalindrome(s) {
  if (s.length < 1) return "";
  let maxSubStart = 0;
  let maxSubLength = 0;
  for (let i = 0; i < s.length; i++) {
    const lengthCenteredAtChar = expandAroundCenter(s, i, i);
    const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
    const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
    if (longestSubAtChar > maxSubLength) {
      maxSubLength = longestSubAtChar;
      maxSubStart = i - Math.floor((maxSubLength - 1) / 2);
    }
  }
  return s.substr(maxSubStart, maxSubLength);
}

We're now done with longestPalindrome(), and we just need to write the function which checks the substring at each center, expandAroundCenter(). expandAroundCenter() will take in the string, a left index, and a right index. We'll want to keep checking the letters at each left and right index to see if they're equal to each other as long as we're within the bounds of the string--so left has to be greater than or equal to 0, and right has to be less than the length of the string. We'll want to have a while loop continue to run so long as the characters at the left and right index are equal to each other, and we're still within the bounds of the string.

function longestPalindrome(s) {
  if (s.length < 1) return "";
  let maxSubStart = 0;
  let maxSubLength = 0;
  for (let i = 0; i < s.length; i++) {
    const lengthCenteredAtChar = expandAroundCenter(s, i, i);
    const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
    const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
    if (longestSubAtChar > maxSubLength) {
      maxSubLength = longestSubAtChar;
      maxSubStart = i - Math.floor((maxSubLength - 1) / 2);
    }
  }
  return s.substr(maxSubStart, maxSubLength);
}

function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    //...
  }
  //...
}

Inside the while loop, all we'll want to do is to continue to expand left and right. That means the left pointer should get smaller (go more toward the left), and the right pointer should get larger (go more toward the right).

Finally, once we're done executing the while loop (we're either out letters in s to check, or we've come to a point where the substring is no longer a palindrome we'll want to return the distance between left and right back to longestPalindrome(). To do this, we can just return right - left - 1.

function longestPalindrome(s) {
  if (s.length < 1) return "";
  let maxSubStart = 0;
  let maxSubLength = 0;
  for (let i = 0; i < s.length; i++) {
    const lengthCenteredAtChar = expandAroundCenter(s, i, i);
    const lengthCenteredAtSpace = expandAroundCenter(s, i, i + 1);
    const longestSubAtChar = Math.max(lengthCenteredAtChar, lengthCenteredAtSpace)
    if (longestSubAtChar > maxSubLength) {
      maxSubLength = longestSubAtChar;
      maxSubStart = i - Math.floor((maxSubLength - 1) / 2);
    }
  }
  return s.substr(maxSubStart, maxSubLength);
}

function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  return right - left - 1;
}

Checking the Code With an Example

With that, we're done writing the solution to this problem. To check how this all works, I like walking through an example. I'll use the string "ABA". Even though the string is short, there are a lot of steps in this algorithm, so walking through it will take a bit of time. Nonetheless, I think it's super valuable to see how an example plays out.

We start with "ABA", and the maxSubStart and maxSubLength both automatically equal 0.

First line is the string "ABA" in bold letters". Beneath that is "maxSubStart = 0" and "maxSubLength = 0".

Now, we'll enter the for loop, and begin checking the character at index 0. We'll call expandAroundCenter() twice, once with left and right both at 0, and once with left at 0 and right at 1.

First line is "ABA", with a blue circle around the first "A". In blue is "i = 0". Beneath that is "expandAroundCenter(”ABA”, 0, 0)" in purple, and beneath that is "expandAroundCenter(”ABA”, 0, 1)" in green.

First we'll call expandAroundCenter where both left and right equal 0. That means the center is the "A" at index 0. Since left is greater than or equal to 0, right is less than the length of the string, and the value at left and right are equal, we'll expand the center.

Now, left is -1 and right is 1. The while loop, however, is no longer true. That means that we won't enter the loop, and will return right - left - 1, which equals 1.

First line is "expandAroundCenter(”ABA”, 0, 0)" in purple. Beneath that is "left = 0" and "right = 0". Then the string "ABA", with a purple vertical line in the middle of the first "A", and a purple horizontal line just beneath that same letter. Beneath that is "left >= 0; right < s.length; s[0] === s[0]". Beneath that is "left = -1; right = 1". Beneath that is the string "ABA", with the same purple vertical line in the middle of the first "A", but now the purple horizontal line extends before the "A" to the blank space, and also covers the "B". Beneath that is "left >= 0" with a red "X" next to it. Beneath that is "return right - left - 1 --> 1 - (-1) - 1 --> 1".

Now we'll call expandAroundCenter with left = 0 and right = 1. That means the center is between "A" and "B". Since the character at the left index does not equal the character at the right index, we won't enter the while loop, and will return 0.

First line is "expandAroundCenter(”ABA”, 0, 1)" in green. Beneath that is "left = 0" and "right = 1". Then the string "ABA", with a green vertical line between the first "A" and "B", and a green horizontal line beneath "A" and "B". Beneath that is "left >= 0; right < s.length; s[0] === s[1]", and a red "X" next to that last clause. Beneath that is "return right - left - 1 --> 1 - 0 - 1 --> 0".

We're back to our function. We can compare the return values of both calls to expandAroundCenter, and since 1 > 0, longestSubAtChar will equal 1. The current maximumSubLength is 0, and since 1 > 0, the maxSubLength will equal 1. We can set maxSubStart equal to 0, as that's the index that the maximum palindromic substring ("A") started at.

First is the string "ABA", with a blue circle around the A, and "i = 0" written in blue beneath it. Beneath that is <br>
"expandAroundCenter(”ABA”, 0, 0) = 1" written in purple and "expandAroundCenter(”ABA”, 0, 1) = 0" written in green. Beneath that, in orange, is "longestSubAtChar = 1; maxSubLength = 0; longestSubAtChar > maxSubLength". Beneath that is "maxSubLength = longestSubAtChar = 1; maxSubStart = 0 - Math.floor((1 - 1)/2) = 0."

We can move on to checking "B" at index 1. We'll call expandAroundCenter twice, once where the center is the letter "B", and once where the center is the space between "B" and the next letter "A".

First line is "ABA", with a blue circle around "B". In blue is "i = 1". Beneath that is "expandAroundCenter(”ABA”, 1, 1)" in purple, and beneath that is "expandAroundCenter(”ABA”, 1, 2)" in green.

First we'll check where the center is "B". Left is 1 and right is 1, which are both inside the bounds of the string, and "B" === "B", so we can enter the while loop. We will expand from the center, decrementing left, and incrementing right.

Now left is 0 and right is 2. Both of these values are inside of the bounds of the string, and the characters at these values are equal to each other ("A" === "A"), so we can go through the while loop again.

Now left is -1 and right is 3. Since left is no longer greater than or equal too 0, we don't even have to check the rest of the conditional, because we know we can't enter the while loop. We will return 3 back to the function.

First line is "expandAroundCenter(”ABA”, 1, 1)" in purple. Beneath that is "left = 1" and "right = 1". Then the string "ABA", with a purple vertical line in the middle of the "B", and a purple horizontal line just beneath that same letter. Beneath that is "left >= 0; right < s.length; s[1] === s[1]". Beneath that is "left = 0; right = 2". Beneath that is the string "ABA", with the same purple vertical line in the middle of the "B", but now the purple horizontal line extends to the left and right to cover the full string, "ABA". Beneath that is "left >= 0; right < s.length; s[2] === s[0]". Beneath that is "left = -1; right = 3". Beneath that is the string "ABA", with the same purple vertical line in the middle of the "B", but now the horizontal line extends to the white space to the left and right of the string. Beneath that is "left >= 0" with a red "X" next to it. Beneath that is "return right - left - 1 --> 3 - (-1) - 1 --> 3".

We'll check where the center is the space between "B" and "A". Left is 1 and right is 2. However, since "B" does not equal "A", we can't enter the while loop, so we'll return 0 to the function.

First line is "expandAroundCenter(”ABA”, 1, 2)" in green. Beneath that is "left = 1" and "right = 2". Then the string "ABA", with a green vertical line between the "B" and second "A", and a green horizontal line beneath "B" and "A". Beneath that is "left >= 0; right < s.length; s[1] === s[2]", and a red "X" next to that last clause. Beneath that is "return right - left - 1 --> 2 - 1 - 1 --> 0".

Now we can compare the return values of both calls to expandAroundCenter. Since 3 is larger than 0, it's the longestSubAtChar. Since 3 is larger than the previous maximum substring (1), 3 becomes the new maxSubLength, and the maxSubStart is 0.

First is the string "ABA", with a blue circle around the B, and "i = 1" written in blue beneath it. Beneath that is <br>
"expandAroundCenter(”ABA”, 1, 1) = 3" written in purple and "expandAroundCenter(”ABA”, 1, 2) = 0" written in green. Beneath that, in orange, is "longestSubAtChar = 3; maxSubLength = 1; longestSubAtChar > maxSubLength". Beneath that is "maxSubLength = longestSubAtChar = 3; maxSubStart = 1 - Math.floor((3 - 1)/2) = 0."

We can move to the last letter of the string, "A", and i = 2. We'll again call "expandAroundCenter" twice, once for each potential "center".

First line is "ABA", with a blue circle around the second "A". In blue is "i = 2". Beneath that is "expandAroundCenter(”ABA”, 2, 2)" in purple, and beneath that is "expandAroundCenter(”ABA”, 2, 3)" in green.

First we'll look at the substring which is centered around A. Left = 2 and right = 2 (both inside the confines of the string), and "A" === "A", so we can enter the while loop and expand from the center.

Now left is 1 and right is 3. Even though left is greater than 0, right is outside the confines of the string, so we can't enter the while loop. We'll return 1 to the function.

First line is "expandAroundCenter(”ABA”, 2, 2)" in purple. Beneath that is "left = 2" and "right = 2". Then the string "ABA", with a purple vertical line in the middle of the second "A", and a purple horizontal line just beneath that same letter. Beneath that is "left >= 0; right < s.length; s[2] === s[2]". Beneath that is "left = 1; right = 3". Beneath that is the string "ABA", with the same purple vertical line in the middle of the first "A", but now the purple horizontal line extends before the "A" to the "B", and to the blank space to the right. Beneath that is "left >= 0; right < s.length" with a red "X" next to the last clause. Beneath that is "return right - left - 1 --> 3 - 1 - 1 --> 1".

We'll now call expandAroundCenter with left = 2 and right = 3. Since 3 is larger than the length of the string, we won't enter the while loop. We can return 0 to the function.

First line is "expandAroundCenter(”ABA”, 2, 3)" in green. Beneath that is "left = 2" and "right = 3". Then the string "ABA", with a green vertical line between the second "A" and the white space that follows the string. and a green horizontal line beneath "A" and trailing white space. Beneath that is "left >= 0; right < s.length", and a red "X" next to that last clause. Beneath that is "return right - left - 1 --> 3 - 2 - 1 --> 0".

Back in the function, we can compare the two longest substrings at this index in the string. The longest one is 1 character long (the letter "A"). Since 1 is not larger than the existing maximum substring length, we won't change the maximum substring values.

Since we're done checking the characters of the string, we can return the maximum substring--it starts at index 0, and is three characters long, which is "ABA".

First is the string "ABA", with a blue circle around the second "A", and "i = 2" written in blue beneath it. Beneath that is <br>
"expandAroundCenter(”ABA”, 2, 2) = 1" written in purple and "expandAroundCenter(”ABA”, 2, 3) = 0" written in green. Beneath that, in orange, is "longestSubAtChar = 1; maxSubLength = 3; longestSubAtChar > maxSubLength", with a red "X" next to the last clause. Beneath that is "return 'ABA'.substr(0, 3); return 'ABA'".

--

Please let me know if you have any questions or alternative solutions to this problem!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide
 

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;
}
 

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

 

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

 

Nice post, made me think if there are asymptotically faster options. The best I could do was O(n log n) by binary searching and doing polymorphic hashing, which is only probibalistic. It would only give false positives though, so you could check. You did specify a max length, though, so O(n^2) is maybe even faster in this case, if the loops are unrolled and cache is good or something.