Palindromic Substrings | Blueprint | Palindrome Problems | 4 Approaches | Leetcode 647
323iPad PDF Notes - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad%20PDF%20Notes/Leetcode-647-Palindromic%20Substrings.pdf
Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 87th Video of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will try to solve a very good String DP problem - Palindromic Substrings | Leetcode 647
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 : Palindromic Substrings | Leetcode 647
Company Tags : Google
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/DP%20on%20Strings/Palindromic%20Substrings.cpp
Leetcode Link : https://leetcode.com/problems/palindromic-substrings/description/
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approaches Summary :
Approach-1 (Simply check all substrings possible)
Idea: Iterate through all possible substrings and check if each one is a palindrome.
Time Complexity (T.C): O(n^3) - Check all substrings, and for each substring, check if it's a palindrome in O(n) time.
Space Complexity (S.C): O(1) - No additional space is used, only a constant amount.
Approach-2 (Memoize the approach above)
Idea: Use memoization to avoid redundant computations when checking if substrings are palindromes.
Time Complexity (T.C): O(n^2) - Every subproblem is computed only once, and after that, it's reused.
Space Complexity (S.C): O(n^2) - Memoization table to store intermediate results.
Approach-3 (Bottom-Up - Blueprint for Palindrome Questions)
Idea: Build a table of whether substrings are palindromes bottom-up, considering all possible lengths.
Time Complexity (T.C): O(n^2) - Iterate through all substrings, and for each, compute the palindrome table in O(1) time.
Space Complexity (S.C): O(n^2) - Palindrome table to store results.
Approach-4 (Smart Approach - Expanding from Center)
Idea: For each character and pair of consecutive characters, expand outward to find palindromes.
Time Complexity (T.C): O(n^2) - Expand around each character or pair of characters in O(n) time.
Space Complexity (S.C): O(1) - No additional space is used, only a constant amount.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
02:36 Brute Force without memoization
10:12 Brute Force with memoization
18:02 Dynamic Programming - Bottom Up
Approach
45:06 Expanding from midpoint of palindrome for Even and Odd length palindrom (Smart
Approach)
#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 #2024 #newyear