Minimum Window Subsequence - Sliding Window - Visualization - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given two strings S and T, find the minimum window in S which will contain all the characters in T in the same order (as a subsequence).

If there is no such window in S that covers all characters in T, return an empty string. If multiple such windows exist, return the one with the smallest starting index.

Input: S = "abcdebdde", T = "bde"
Output: "bcde"

Examples❯

S T Output Description
"abcdebdde" "bde" "bcde" Normal case where 'bde' appears as a subsequence in multiple places; the shortest window is 'bcde'
"jmeqksfrsdcmsiwvaovztaqenprpvnbstl" "k" "k" Single character match; smallest valid window is just that character
"abc" "ac" "abc" 'ac' appears in order in 'abc', so the entire string is the minimum window
"abc" "d" "" 'd' does not exist in 'abc', so no window can be formed
"abcdebdde" "e" "e" Target is a single character that appears in 'S'; output is smallest such occurrence
"abcbcde" "bde" "bcde" Multiple b’s and c’s; valid minimum window is found correctly despite repetitions
"abcde" "abcde" "abcde" Entire 'T' is exactly 'S'; return full string
"abcde" "edc" "" 'edc' appears in reverse order in 'S', so it's not a subsequence; return empty string
"" "abc" "" Empty source string; cannot contain any subsequence
"abcde" "" "" Empty target; no valid non-empty window can contain an empty sequence in this context

Solution❯

Understanding the Problem

We are given two strings S and T. Our goal is to find the smallest window in S such that all characters of T appear in order as a subsequence.

A subsequence means the characters of T must appear in S in the same order, but not necessarily consecutively.

If there are multiple valid windows, we return the one that starts first. If there is no such window, we return an empty string.

Step-by-Step Solution with Example

Step 1: Understand the Example

S = "abcdebdde", T = "bde"

We need the shortest substring of S that contains 'b', then 'd', then 'e' in order.

Answer: "bcde" is the smallest valid window.

Step 2: Two Pointers Technique

We use two pointers:

  • A forward pointer i that scans through S
  • A second pointer j that walks through T to match the subsequence

Step 3: Forward Scan

We move i from left to right through S. Each time S[i] matches T[0], we try to match the full T subsequence from that point onward.

Step 4: Match the Entire T

Once T is fully matched by advancing both i and j, we record the end position (where the match finishes in S).

Step 5: Backward Shrink to Minimize Window

We now try to shrink the window by moving backward from end using a new pointer. We go backwards matching characters of T in reverse order to find the start of this minimum window.

Step 6: Update Minimum Window

If the window found is smaller than the previously recorded one, we update our result (minimum length and starting index).

Step 7: Continue Search

We move forward in S and repeat the process until we reach the end of S.

Step 8: Return Result

If a valid window was found, return the substring. Otherwise, return "".

Edge Cases

  • T is longer than S → Impossible to form a window → Return ""
  • T is empty → By definition, every string contains an empty subsequence → Return "" or handle based on constraints
  • Multiple windows found → Return the one with the smallest start index
  • No match found → Return empty string

Final Thoughts

This problem is a great example of combining the sliding window and two-pointer technique to solve subsequence matching problems efficiently. The key idea is to move forward to find a valid window, and then move backward to minimize it. This technique avoids checking all substrings and saves time.

With a clear understanding of how to scan forward and shrink backward, we can handle both normal and edge cases smoothly.

Algorithm Steps❯

  1. Initialize variables: start = 0 and minLen = infinity to track the minimum window.
  2. Use a forward pointer i to traverse string S.
  3. When S[i] matches the first character of T, attempt to find a full match of T in S starting from i.
  4. → Use a second pointer j to walk through T while i moves forward to match each character.
  5. → If all characters of T are matched, track the ending index end and begin shrinking the window backwards from end to find the leftmost start that still keeps T in order.
  6. → Use reverse pointers to backtrack and identify the minimum window start and update minLen and start if the current window is smaller.
  7. Continue until the end of S is reached.
  8. Return S.substr(start, minLen) if minLen != infinity, otherwise return "".

Code

Python
Java
JS
C
C++
Go
Rust
Kotlin
Swift
TS
def min_window_subsequence(S: str, T: str) -> str:
    n, m = len(S), len(T)
    min_len = float('inf')
    start = 0

    i = 0
    while i < n:
        if S[i] == T[0]:
            t_idx = 0
            j = i
            # Forward match to find subsequence
            while j < n and t_idx < m:
                if S[j] == T[t_idx]:
                    t_idx += 1
                j += 1
            if t_idx == m:  # Full match found
                end = j - 1
                # Backward shrink to find minimal start
                t_idx = m - 1
                k = end
                while k >= i:
                    if S[k] == T[t_idx]:
                        t_idx -= 1
                        if t_idx < 0:
                            break
                    k -= 1
                window_len = end - k + 1
                if window_len < min_len:
                    min_len = window_len
                    start = k
                i = k  # Move i to start of found window
        i += 1

    return S[start:start+min_len] if min_len != float('inf') else ""

# Example usage
S = "abcdebdde"
T = "bde"
print(min_window_subsequence(S, T))  # Output: "bcde"

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n * m)In the best case, for each character in S, we may have to scan up to all characters in T (size m). Even if we find a match early, we still potentially do m comparisons per n characters in S.
Average CaseO(n * m)On average, the algorithm needs to traverse the string S and, for each starting match, walk through T (size m) and then potentially backtrack to minimize the window. This results in a nested O(n * m) pattern.
Worst CaseO(n * m)In the worst case, for each character in S (size n), we have to scan through all of T (size m) to check for a subsequence match, and then walk backward to find the optimal window start. This results in O(n * m) time.

Space Complexity❯

O(1)

Explanation: Only a few pointers and constant variables are used for tracking the window and indices. No additional space is required proportional to the size of input strings.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...