Find Longest Special Substring That Occurs Thrice I & II | Leetcode 2981 & 2982 | codestorywithMIK
471iPad PDF Notes - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/iPad PDF Notes/Leetcode 2981 & 2982.pdf
Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 53rd Video of our Playlist "Strings" by codestorywithMIK
In this video we will try to solve a good string problem : Find Longest Special Substring That Occurs Thrice I & II | 3 Detailed Approaches | Leetcode 2981 & 2982 | 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 : Find Longest Special Substring That Occurs Thrice I & II | 3 Detailed Approaches | Leetcode 2981 & 2982 | codestorywithMIK
Company Tags : will update later
My solutions on Github(C++ & JAVA) - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/strings/Find Longest Special Substring That Occurs Thrice I & II.cpp
Leetcode Link : https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-i
: https://leetcode.com/problems/find-longest-special-substring-that-occurs-thrice-ii
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/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Brute Force - Try All Possible Substrings
Time Complexity: O(n^3)
Space Complexity: O(n^2)
This approach generates all possible substrings of the input string and checks for valid ones. For each substring, it counts the occurrences in the string using a map. The maximum valid substring length (frequency ≥ 3) is tracked.
Approach 2: Better Brute Force
Time Complexity: O(n^2)
Space Complexity: O(n^2) (due to the map storing substring lengths and counts)
Instead of storing the entire substring, this approach uses a map where the key is a pair of the character and the substring length. For each position in the string, it counts the consecutive identical characters and updates the map. The cumulative counts are then used to find the maximum valid substring length.
Approach 3: Optimal - Using a 2D Matrix
Time Complexity: O(n)
Space Complexity: O(26*n)∼O(n)
This approach uses a 2D matrix where each row corresponds to a character ('a' to 'z') and each column tracks the frequency of substrings of a specific length. The input string is traversed once to fill the matrix. Cumulative frequencies are calculated in reverse to efficiently determine the maximum valid substring length.
✨ Timelines✨
00:00 - Introduction
0:45 - Motivation
1:19 - Problem Explanation
5:15 - Approach-1 Brute Force
10:01 - Coding Approach-1
14:34 - Approach-2 Better Brute Force
25:50 - Coding Approach-2
28:43 - Approach-3 Optimal
54:44 - Coding Approach-3
#MIK #mik #Mik
#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 #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codestorywithmk #codestorywitmick #codestorwithmik