Longest Palindromic Substring🖌

Question

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

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Java Solution

Two different solutions with two different time complexities

O(n³)
For a string n (where n is the size of string), the below code will generate/check every possible substring and on each of that substrings, it will check if it's a palindrome which will take O(n/2) Or o(n). So for generating every possible substring simple brute force will take O(n²) and since on each substring im checking if it's a palindrome that will take O(n). Combining the both we get O(n³)

Code

O(n²)
At the top, I'm going through all the elements in a string so O(n) for that. And on each loop, I'm going to go through the whole string again (in the worst case) for that another O(n). Combining both we get O(n²).

Code