Problem

Given strings s1 and s2, return _the minimum contiguous substring part of _s1 , so thats2 is a subsequence of the part.

If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

Examples

Example 1:

1
2
3
4
5

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of s2 in the window must occur in order.

Example 2:

1
2

Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""

Constraints:

  • 1 <= s1.length <= 2 * 10^4
  • 1 <= s2.length <= 100
  • s1 and s2 consist of lowercase English letters.

Solution

Method 1 – Two Pointers with Backtracking

Intuition

To find the minimum window in s1 containing s2 as a subsequence, we scan s1 to find the end of a valid window, then backtrack to find its start. By repeating this process, we can find the smallest such window efficiently.

Approach

  1. Use two pointers: one to scan s1 and one to scan s2.
  2. Move forward in s1 until all of s2 is matched as a subsequence.
  3. Once matched, backtrack in s1 to find the leftmost start of the window.
  4. Track the minimum window found and repeat until the end of s1.
  5. Return the smallest window or empty string if none found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    string minWindow(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        int min_len = INT_MAX, start = -1;
        for (int i = 0; i < m; ++i) {
            if (s1[i] != s2[0]) continue;
            int j = i, k = 0;
            while (j < m && k < n) {
                if (s1[j] == s2[k]) ++k;
                ++j;
            }
            if (k == n) {
                int end = j - 1;
                k = n - 1;
                j = end;
                while (j >= i) {
                    if (s1[j] == s2[k]) {
                        if (--k < 0) break;
                    }
                    --j;
                }
                if (end - j < min_len) {
                    min_len = end - j;
                    start = j + 1;
                }
            }
        }
        return start == -1 ? "" : s1.substr(start, min_len);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func MinWindow(s1, s2 string) string {
    m, n := len(s1), len(s2)
    minLen, start := m+1, -1
    for i := 0; i < m; i++ {
        if s1[i] != s2[0] {
            continue
        }
        j, k := i, 0
        for j < m && k < n {
            if s1[j] == s2[k] {
                k++
            }
            j++
        }
        if k == n {
            end := j - 1
            k = n - 1
            j = end
            for j >= i {
                if s1[j] == s2[k] {
                    k--
                    if k < 0 {
                        break
                    }
                }
                j--
            }
            if end-j < minLen {
                minLen = end - j
                start = j + 1
            }
        }
    }
    if start == -1 {
        return ""
    }
    return s1[start : start+minLen]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public String minWindow(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int minLen = Integer.MAX_VALUE, start = -1;
        for (int i = 0; i < m; i++) {
            if (s1.charAt(i) != s2.charAt(0)) continue;
            int j = i, k = 0;
            while (j < m && k < n) {
                if (s1.charAt(j) == s2.charAt(k)) k++;
                j++;
            }
            if (k == n) {
                int end = j - 1;
                k = n - 1;
                j = end;
                while (j >= i) {
                    if (s1.charAt(j) == s2.charAt(k)) {
                        if (--k < 0) break;
                    }
                    j--;
                }
                if (end - j < minLen) {
                    minLen = end - j;
                    start = j + 1;
                }
            }
        }
        return start == -1 ? "" : s1.substring(start, start + minLen);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    fun minWindow(s1: String, s2: String): String {
        val m = s1.length
        val n = s2.length
        var minLen = Int.MAX_VALUE
        var start = -1
        for (i in 0 until m) {
            if (s1[i] != s2[0]) continue
            var j = i
            var k = 0
            while (j < m && k < n) {
                if (s1[j] == s2[k]) k++
                j++
            }
            if (k == n) {
                val end = j - 1
                k = n - 1
                j = end
                while (j >= i) {
                    if (s1[j] == s2[k]) {
                        k--
                        if (k < 0) break
                    }
                    j--
                }
                if (end - j < minLen) {
                    minLen = end - j
                    start = j + 1
                }
            }
        }
        return if (start == -1) "" else s1.substring(start, start + minLen)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def minWindow(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        min_len, start = float('inf'), -1
        i = 0
        while i < m:
            if s1[i] == s2[0]:
                j, k = i, 0
                while j < m and k < n:
                    if s1[j] == s2[k]:
                        k += 1
                    j += 1
                if k == n:
                    end = j - 1
                    k = n - 1
                    j = end
                    while j >= i:
                        if s1[j] == s2[k]:
                            k -= 1
                            if k < 0:
                                break
                        j -= 1
                    if end - j < min_len:
                        min_len = end - j
                        start = j + 1
            i += 1
        return "" if start == -1 else s1[start:start+min_len]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

impl Solution {
    pub fn min_window(s1: String, s2: String) -> String {
        let m = s1.len();
        let n = s2.len();
        let s1_bytes = s1.as_bytes();
        let s2_bytes = s2.as_bytes();
        let mut min_len = usize::MAX;
        let mut start = None;
        for i in 0..m {
            if s1_bytes[i] != s2_bytes[0] {
                continue;
            }
            let (mut j, mut k) = (i, 0);
            while j < m && k < n {
                if s1_bytes[j] == s2_bytes[k] {
                    k += 1;
                }
                j += 1;
            }
            if k == n {
                let end = j - 1;
                k = n - 1;
                j = end;
                while j >= i {
                    if s1_bytes[j] == s2_bytes[k] {
                        if k == 0 { break; }
                        k -= 1;
                    }
                    if j == 0 { break; }
                    j -= 1;
                }
                if end - j < min_len {
                    min_len = end - j;
                    start = Some(j + 1);
                }
            }
        }
        match start {
            Some(idx) => s1[idx..idx+min_len].to_string(),
            None => String::new(),
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    minWindow(s1: string, s2: string): string {
        const m = s1.length, n = s2.length;
        let minLen = Infinity, start = -1;
        for (let i = 0; i < m; i++) {
            if (s1[i] !== s2[0]) continue;
            let j = i, k = 0;
            while (j < m && k < n) {
                if (s1[j] === s2[k]) k++;
                j++;
            }
            if (k === n) {
                const end = j - 1;
                k = n - 1;
                j = end;
                while (j >= i) {
                    if (s1[j] === s2[k]) {
                        if (--k < 0) break;
                    }
                    j--;
                }
                if (end - j < minLen) {
                    minLen = end - j;
                    start = j + 1;
                }
            }
        }
        return start === -1 ? "" : s1.substring(start, start + minLen);
    }
}

Complexity

  • ⏰ Time complexity: O(m * n) — For each position in s1, we may scan up to the length of s2 twice.
  • 🧺 Space complexity: O(1) — Only a few variables are used for computation.