Count Substrings That Satisfy K-Constraint I & II | Detailed Explanation | Leetcode 3258 & 3261
201Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 26th Video of our Playlist "Sliding Window : Popular Interview Problems" by codestorywithMIK
Minimum Falling Path Sum - • Minimum Falling Path Sum | Recursion ...
In this video we will try to solve two very Sliding Window problems : Count Substrings That Satisfy K-Constraint I & II | Detailed Explanation | Leetcode 3258 & 3261 | 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 : Count Substrings That Satisfy K-Constraint I & II | Detailed Explanation | Leetcode 3258 & 3261 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Count Substrings That Satisfy K-Constraint I : https://leetcode.com/problems/count-s...
Count Substrings That Satisfy K-Constraint II : https://leetcode.com/problems/count-s...
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: Brute Force
Time Complexity: O(n²)
Space Complexity: O(1)
Description:
This approach uses nested loops to explore all possible substrings of the string s.
For each starting index i, it iterates over all possible ending indices j and counts the occurrences of '0's and '1's in the substring s[i:j+1].
If the number of '0's or '1's does not exceed the given constraint k, it increments the count of valid substrings.
The loop breaks as soon as the substring becomes invalid, ensuring that unnecessary iterations are avoided.
Drawback: The time complexity is quadratic (O(n²)), making it inefficient for larger strings.
Approach 2: Sliding Window
Time Complexity: O(n)
Space Complexity: O(1)
Description:
This method optimizes the brute-force approach by using a sliding window technique.
It maintains two pointers, i and j, to represent the window of the current substring. It also keeps track of the count of '0's and '1's within this window.
As the window expands by moving j, the counts are updated. If both counts exceed k, the window is shrunk by moving i until it becomes valid again.
The number of valid substrings ending at j is calculated using the difference between i and j.
Advantage: The time complexity is linear (O(n)), making it much more efficient than the brute-force approach.
Approach 3: Sliding Window with Cumulative Sum (Handling Queries)
Time Complexity: O(n + Q), where n is the length of the string and Q is the number of queries.
Space Complexity: O(n)
Description:
This approach extends the sliding window technique to efficiently handle multiple queries.
It first precomputes two arrays, leftMost and rightMost, where leftMost[j] gives the left-most valid index for a substring ending at j, and rightMost[j] gives the right-most valid index for a substring starting at j.
Another array, tempValidSubstr, stores the number of valid substrings ending at each index, and a cumulative sum array cumSum helps in quickly calculating the sum of valid substrings over any given range.
For each query, the method computes the number of valid substrings within the specified range, combining the precomputed cumulative sums and the valid substring lengths.
✨ 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