Leetcode Problem 727. Minimum Window Subsequence

Algorithm

1. Initialize an empty string answer to store the result.
2. Create a dictionary indices to store lists of indices for each character in s1.
3. Populate indices with the positions of each character in s1.
4. Initialize an array ind of size m with zeros to track the current index for each character in s2.
5. Iterate start from 0 to n - 1.
   • Set prev to start - 1.
   • Iterate j from 0 to m - 1.
     • Let curIndices be indices[s2[j]].
     • Increment ind[j] until curIndices[ind[j]] > prev.
     • If ind[j] equals the length of curIndices, break and continue with the next start.
     • Update prev to curIndices[ind[j]].
   • If a valid window is found, update answer if it is empty or the current window is smaller.
6. Return answer.