Longest Palindromic Subsequence | Using Blue Print | DP On Strings | Leetcode 516 | DP Concepts - 25

Channel:

codestorywithMIK

Subscribers:

92,300

Published on June 30, 2024 12:00:00 AM ● Video Link: https://www.youtube.com/watch?v=WIhQ5NOzCKM

Duration: 17:04

2,037 views

72

iPad PDF NOTES - https://github.com/MAZHARMIK/Intervie...
Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 25th Video of our Playlist "DP Concepts & Qns" by codestorywithMIK

Longest Palindromic Subsequence Recursion + Memo & Different Bottom Up -    • Longest Palindromic Subsequence | Rec...  

This is the seventh video of the "DP On Strings" series in this playlist.
In this video we will try to solve a good DP on strings problem : Longest Palindromic Subsequence | Using Blue Print | DP On Strings | Leetcode 516 | DP Concepts & Qns-25 | codestorywithMIK


I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Longest Palindromic Subsequence | Using Blue Print | DP On Strings | Leetcode 516 | DP Concepts & Qns-25 | codestorywithMIK
Company Tags : Amazon, LinkedIn, Paypal, Rivigo, Uber, Google
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/longest...


My DP Concepts Playlist :    • Roadmap for DP | How to Start DP ? | ...  
My Graph Concepts Playlist :    • Graph Concepts & Qns - 1 : Graph will...  
My Segment Tree Concepts Playlist :    • Segment Tree | Introduction | Basics ...  
My Recursion Concepts Playlist :    • Introduction | Recursion Concepts And...  
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram :   / codestorywithmik  
Facebook :   / 100090524295846  
Twitter :   / cswithmik  
Subscribe to my channel :    / @codestorywithmik  

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝


Approaches Summary :
The approach to finding the longest palindromic subsequence (LPS) in a given string uses dynamic programming. Here's a summary of the steps involved:

Initialization:
Create a 2D array t where t[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j].
Initialize the diagonal of the array (t[i][i]) to 1, since any single character is a palindrome of length 1.

Filling the DP Table:
Iterate over all possible lengths of substrings from 2 to n (the length of the string).
For each length L, iterate over all possible starting indices i of the substrings, and compute the ending index j as i + L - 1.

Subsequence Matching:
If the characters at the start and end of the current substring (s[i] and s[j]) are the same, then t[i][j] = 2 + t[i + 1][j - 1].
If they are different, then t[i][j] = max(t[i][j - 1], t[i + 1][j]).
Result:

The length of the longest palindromic subsequence for the entire string is stored in t[0][n - 1].

✨ Timelines✨
00:00 - Introduction
02:40 - Recap Recursion + Memoization
07:21 - Blue Print bottom Up
15:10 - Coding Bottom Up (Blue Print)

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024