Problem statement

https://binarysearch.com/problems/Shortest-Window-Substring-in-Order/

Solution

Equal to Leetcode 0727 Minimum Window Subsequence, but here we need even faster algorithm. The idea is similar to Leetcode 1955. Count Number of Special Subsequences, here we need to find the shortest substring which have 0, 1, ..., 25 as subsequence. Here important thing is that all elements of [0, 1, ..., 25] are different, and we can use dp of size 26, where we keep if dp[i] the rightest place of subsequence [0, ..., i] so far. When we have new symbol x, we can update dp[x] as max(dp[x], dp[x-1]).

Complexity

It is O(n) for time and O(m) for space.

Code

class Solution:
    def solve(self, s):
        s = [ord(x) - 97 for x in s]
        ans = INF = float("inf")
        dp = [-INF] * 26
        for i, x in enumerate(s):
            dp[x] = max(dp[x], dp[x - 1])
            if x == 0: dp[x] = i
            ans = min(ans, i - dp[25] + 1)
        return ans if ans < INF else -1