Strings: Longest Palindromic Substring

Longest Palindromic Substring problem on Leetcode

As I start to continue to prepare for technical interviews, I’ll be going over solutions for questions that I find initially challenging. Today, I’ll be going over the Longest Palindromic Substring problem on Leetcode. The problem can be found here.

Problem Description

Given a string s, return the longest palindromic substring in s.

Example 1:
Input: s = "babad", Output: "bab", Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd", Output: "bb"
Example 3:
Input: s = "a", Output: "a"

Brute Force Solution

The naive way to solve this problem is to find all substrings by considering every possible start and end position and verify that it’s a palindrome. In the end, return the longest palindrome you found. The time complexity of this solution is O(n³). Let’s see why.

What does this code do?