iamrahulroy · April 19, 2024 13:19 · Apr 19, 2024
diff --git a/min_substring_window.rb b/min_substring_window.rb
@@ -0,0 +1,45 @@
+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