DP-10: Longest Palindromic Substring

Source Code:https://thecodingsimplified.com/longest-palindromic-substring
Solution - 1: Recursive Basic Solution
- We start from start = 0 & end = length - 1
- If values at start & end indexes are equal then recursively check for middle & if length matches then only it's part of lps
- It's not matching, then Get the maximum of lps(start, end - 1), lcs(start + 1, end)

Time Complexity: O(2^n)
Space Complexity: O(n)

Solution - 2: Top Down DP Solution
- We start from start = 0 & end = length - 1 & initialize a 2D array
- If values at start & end indexes are equal then recursively check for middle & if length matches then only it's part of lps
- It's not matching, then Get the maximum of lps(start, end - 1), lcs(start + 1, end)
- At every position we check, if value is null means we need to find the value, if it's not null then value
exists in array & return from array.

Time Complexity: O(n * n)
Space Complexity: O(n * n)

Solution - 3: Bottom UP DP Solution
- We initialize 2D array & represent string in 2D form
- for diagonal, we set as true
- We start 1 loop starting from 2nd last row (i) & another loop from j = i + 1, which'll check every combination
- If value matches & if arr[start + 1][end - 1] also matches, then only it's part of lps, so maxLPS = end - start + 1
- If not matching, then it'll be set as false
- at last we return maxLPS

Time Complexity: O(n * n)
Space Complexity: O(n * n)

Do Watch video for more info

CHECK OUT CODING SIMPLIFIED
https://www.youtube.com/codingsimplified

★☆★ VIEW THE BLOG POST: ★☆★
http://thecodingsimplified.com

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★
https://www.youtube.com/codingsimplif...

★☆★ Send us mail at: ★☆★
Email: thecodingsimplified@gmail.com

Видео DP-10: Longest Palindromic Substring канала Coding Simplified