Longest Palindromic Substring🖌
Given a string
s, return the longest palindromic substring in
Input: s = "babad"
Explanation: "aba" is also a valid answer.
Input: s = "cbbd"
1 <= s.length <= 1000
sconsist of only digits and English letters.
Two different solutions with two different time complexities
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³)
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²).