Longest Palindrome | 3 Easy Approaches | Leetcode 409 | codestorywithMIK
251Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 40th Video of our Playlist "Leetcode Easy : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good practice String problem : Longest Palindrome | 3 Easy Approaches | Leetcode 409 | 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 Palindrome | 3 Easy Approaches | Leetcode 409 | codestorywithMIK
Company Tags : will update soon
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 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
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Using a Set
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(n)
Method:
Initialize an empty set to track characters.
Traverse the string and for each character, check if it is already in the set.
If it is, remove it from the set and increment the result by 2.
If it is not, add it to the set.
If the set is not empty at the end, add 1 to the result to account for one central character.
Summary: This approach leverages a set to find pairs of characters. Each time a pair is found, it contributes 2 to the palindrome length. If there are any leftover characters, one can be used as the center of the palindrome.
Approach 2: Using a HashMap and Counting Frequency
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(n)
Method:
Initialize a HashMap to count the frequency of each character in the string.
Traverse the HashMap to accumulate the length of characters that can be fully paired.
For each character count, add the even part to the result.
Track if there is any character with an odd count.
If there is a character with an odd count, add 1 to the result for the central character.
Summary: This approach uses a HashMap to count frequencies of characters. Even frequencies are directly added to the result, while odd frequencies contribute one less than their count to maintain pairs, with the possibility of using one odd character as the center.
Approach 3: One Iteration
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(n)
Method:
Initialize a HashMap to count the frequency of each character and an odd frequency counter.
Traverse the string and update the frequency of each character in the HashMap.
Adjust the odd frequency counter based on whether the current frequency is odd or even.
Calculate the result based on the total length minus the number of odd frequencies plus one (if any odd frequency exists).
Summary: This approach combines counting character frequencies with tracking the number of characters that have odd frequencies in a single pass through the string. The result is calculated by subtracting the number of odd frequencies from the total length and adding one if any odd frequencies exist, ensuring the longest possible palindrome.
All three approaches efficiently calculate the length of the longest palindrome that can be formed from a given string, each with a time complexity of O(n) and space complexity of O(n). The choice between them depends on the preferred data structures and slight variations in implementation.
✨ Timelines✨
00:00 - Introduction
#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
Other Videos By codestorywithMIK
Other Statistics
Counter-Strike: Source Statistics For codestorywithMIK
At this time, codestorywithMIK has 34,577 views for Counter-Strike: Source spread across 5 videos. Less than an hour worth of Counter-Strike: Source videos were uploaded to his channel, making up less than 0.10% of the total overall content on codestorywithMIK's YouTube channel.