Minimum Window Subsequence

Photo by William Daigneault on Unsplash

Given strings s1 and s2, return the minimum contiguous substring part of s1, so that s2 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.

Example 1:

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:

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

Constraints:

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

Solution

Initially, we can search for the first occurrence of the subsequence. Then, we can find the subsequence in the opposite direction to find the smaller one. For example, if we have s2= ab and s1= acab, the first occurrence would result in acab, and we’ll start searching in the opposite direction. When b is matched, we’ll look for the most recent a in s2, which will give us ab as our final result. We can then apply this method to bigger strings as well.

The following illustration might clarify this process.

Let’s see how we might implement this functionality:

  1. Traverse the s1 string, and for each letter, check if it’s equal to the current letter in s2.
  2. If the letters are equal, move to the next letter in both the strings.
  3. When the last letter of s2 is matched with a letter of s1, mark that letter position of s1 as a possible window.
  4. Now, go backward from the end of s1 and match the letters with s2 from the marked position. Do this until the s1 string is exhausted.
  5. Check if your current window is smaller than the previous one. If yes, mark it as the minimum window.
  6. Repeat from step 2 until you reach the end of s1.

Let’s look at the code for the solution below:

Time complexity

The time complexity will be O(S×T).

Space complexity

The space complexity will be O(1) because the program uses constant space.

If you like the content please follow me here @medium and at LinkedIn

https://www.linkedin.com/in/jaydeep-shil-75a90847

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Your go to Numpy checklist

Best of all worlds — monitoring Envoy’s activity using Hystrix dashboard

The risks of using custom extensions with formal standards

Logitech MX Keys Mini | Logi Bolt USB Receiver | Linux

[Hardware Design III] Configurable Designs

Build fast and better Apps with SwiftUI

Stuck in a Rut? — Three Extreme Ways to Rekindle your Programmer Spirit

Deploying Open Source Observability Stack in AWS — Part — II

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

ZigZag Conversion — LeetCode Solutions

What happens in a technical interview?

Leetcode 1282. Group the People Given the Group Size They Belong To

My interview experience with Publicis Sapient (got selected!!)