Problem

  • Given two strings s of length m and t of length n
  • Find a minimum substring in s which contains all characters in t

Example

  • Input: given two strings aaaaaaaaaaaabbbbbcdd and abcdd
  • Expected output: abbbbbcdd

Approach: Sliding Window

Iterating over s window by window with two index pointers i and j to find the minimum substring

Implementation


Complexity

  • Time complexity: O(m+n)
  • Space complexity: O(m+n)