Wezual Code

Minimum Window Substring: Efficient Algorithm for Finding the Shortest Substring

author
Digambar Patil

The Minimum Window Substring problem is a classic string manipulation challenge that tests our algorithmic skills. In this blog, we will explore an efficient solution to find the minimum window substring in a given string. We will provide implementation examples in both Java and Python, enabling you to grasp the concepts and apply them to your own coding projects.

 

Understanding the Problem:

Given a string and a target pattern, our objective is to find the minimum window substring in the given string that contains all the characters of the target pattern. The minimum window substring refers to the shortest possible substring that satisfies this condition.

 

Approach:

To solve the Minimum Window Substring problem, we can use the sliding window technique. This approach involves maintaining a window of characters in the string and adjusting its size based on certain conditions. The key steps of the algorithm are as follows:

  1. Create two pointers, left and right, to define the window boundaries.
  2. Move the right pointer to expand the window until it contains all the characters of the target pattern.
  3. Once a valid window is found, move the left pointer to minimize the window size while still meeting the condition.
  4. Keep track of the minimum window size and its starting and ending indices.
  5. Repeat steps 2 to 4 until the right pointer reaches the end of the string.

 

Example:

Let's illustrate the algorithm with an example:

String: "ADOBECODEBANC" Target Pattern: "ABC"

  1. Initially, the window is empty, and we move the right pointer to find a valid window that contains "ABC" characters. In this case, we find the window "ADOBEC" as the first valid window. We update the minimum window size and its indices accordingly.
  2. Next, we move the left pointer to minimize the window size while still containing all the characters. The window becomes "DOBEC" after moving the left pointer. We continue this process, updating the minimum window size and indices whenever we find a smaller valid window.
  3. Finally, we reach the end of the string, and the minimum window substring is "BANC" with a length of 4.

 

Java Implementation:

Let's begin with the Java implementation of finding the minimum window substring:

public class MinimumWindowSubstring {
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0)
            return "";

        int[] targetCounts = new int[128];
        for (char c : t.toCharArray()) {
            targetCounts[c]++;
        }

        int left = 0, right = 0, minLen = Integer.MAX_VALUE;
        int minStart = 0, count = t.length();

        while (right < s.length()) {
            char rightChar = s.charAt(right);
            if (targetCounts[rightChar] > 0) {
                count--;
            }
            targetCounts[rightChar]--;

            while (count == 0) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }

                char leftChar = s.charAt(left);
                targetCounts[leftChar]++;
                if (targetCounts[leftChar] > 0) {
                    count++;
                }
                left++;
            }

            right++;
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";

        String minWindowSubstring = minWindow(s, t);
        System.out.println("Minimum Window Substring: " + minWindowSubstring);
    }
}

 

Python Implementation:

Next, let's explore the Python implementation of finding the minimum window substring:

def minWindow(s: str, t: str) -> str:
    if not s or not t:
        return ""

    target_counts = {}
    for char in t:
        target_counts[char] = target_counts.get(char, 0) + 1

    left, right = 0, 0
    min_len = float("inf")
    min_start = 0
    count = len(t)

    while right < len(s):
        if s[right] in target_counts:
            if target_counts[s[right]] > 0:
                count -= 1
            target_counts[s[right]] -= 1

        while count == 0:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_start = left

            if s[left] in target_counts:
                target_counts[s[left]] += 1
                if target_counts[s[left]] > 0:
                    count += 1
            left += 1

        right += 1

    return s[min_start: min_start + min_len] if min_len != float("inf") else ""
    
s = "ADOBECODEBANC"
t = "ABC"

min_window_substring = minWindow(s, t)
print("Minimum Window Substring:", min_window_substring)

 

Conclusion:

In this blog, we explored an efficient approach to solve the Minimum Window Substring problem using the sliding window technique. We provided implementation examples in both Java and Python, empowering you to understand the concept and apply it to your own projects. By mastering this problem, you enhance your algorithmic skills and gain valuable insights into string manipulation. Feel free to experiment with different input cases and further optimize the code for your specific requirements.

Sliding Window
Hash Table
String