Created
April 19, 2024 13:19
-
-
Save iamrahulroy/b76a01d7f15d2a89d3f19ec2e446c845 to your computer and use it in GitHub Desktop.
Find minimum substring that has all the distinct chars
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def min_substring_window(s, distinct) | |
| return "" if distinct.empty? | |
| # Count the frequency of characters in distinct | |
| count_distinct = Hash.new(0) | |
| distinct.each { |char| count_distinct[char] += 1 } | |
| # Maintain current window count, chars we have and chars we need count | |
| window = Hash.new(0) | |
| have = 0 | |
| need = count_distinct.length | |
| # Initialize result variables | |
| res = [-1, -1] | |
| result_length = Float::INFINITY | |
| left = 0 # Left pointer of the window | |
| (0..s.length - 1).each do |right| | |
| # Expand the window to the right | |
| char = s[right] | |
| window[char] += 1 | |
| have += 1 if count_distinct.key?(char) && window[char] == count_distinct[char] | |
| # Compress the window from the left as much as possible while maintaining the constraints | |
| while have == need | |
| # Update the result if the current window is smaller | |
| if right - left + 1 < result_length | |
| res = [left, right] | |
| result_length = right - left + 1 | |
| end | |
| # Compress the window from the left | |
| window[s[left]] -= 1 | |
| have -= 1 if count_distinct.key?(s[left]) && window[s[left]] < count_distinct[s[left]] | |
| left += 1 | |
| end | |
| end | |
| # Extract and return the minimum window if found, otherwise return an empty string | |
| if result_length != Float::INFINITY | |
| return s[res[0]..res[1]] | |
| else | |
| return "" | |
| end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment