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

Localization Changes in Java 9

Renovate: Dependency Management

Is GNOME Theming Dead ..or Not?

How to implement flow coordinator pattern

Use of @Async asynchronous method + @Transactional transaction processing

Getting started with Domain and Hosting for your website

We Are Millions building a better Web

We are millions building a better web

Mastering In CoreData (Part 9 NSFetchRequest)

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

Time Based Key-Value Store

Anatomy of a System Design Interview

Level up your System Design Interview: Drive the conversation

CRACKING THE SYSTEM DESIGN INTERVIEW — The Plan