Python: Find the minimum window in a given string which will contain all the characters of another given string

Last update on December 21 2024 07:46:57 (UTC/GMT +8 hours)

Minimum window with all chars of another string.

Write a Python program to find the minimum window in a given string that will contain all the characters of another given string.

Visual Presentation:

Example 1
Input
str1 = " PRWSOERIUSFK "
str2 = " OSU "
Output:
Minimum window is "OERIUS"

Sample Solution:

Python Code:

import collections

# Function to find minimum window substring
def min_window(str1, str2):

  # Store characters and length of str2
  result_char, missing_char = collections.Counter(str2), len(str2)  

  i = p = q = 0

  # Iterate through str1
  for j, c in enumerate(str1, 1):

    # Decrement missing characters
    missing_char -= result_char[c] > 0  
    result_char[c] -= 1

    # If all chars found, optimize window
    if not missing_char:

      # Remove extra characters from left  
      while i < q and result_char[str1[i]] < 0:
        result_char[str1[i]] += 1
        i += 1

      # Update window if new is smaller
      if not q or j - i <= q - p:
        p, q = i, j

  # Return minimum window 
  return str1[p:q]

# Test strings
str1 = "PRWSOERIUSFK"
str2 = "OSU"

# Print original strings
print("Original Strings:\n",str1,"\n",str2)

# Print message
print("Minimum window:")

# Print result
print(min_window(str1,str2)) 

Sample Output:

Original Strings:
 PRWSOERIUSFK 
 OSU
Minimum window:
OERIUS

Flowchart:

Python Code Editor:

Previous: Write a Python program to count Uppercase, Lowercase, special character and numeric values in a given string.
Next: Write a Python program to find smallest window that contains all characters of a given string.