# Is there a linear-time solution to the minimum window substring problem, provided the characters in the substring must be in order?

Suppose there are two strings, $$S$$ and $$T$$, and we want to find the length $$l$$ of the shortest substring of $$S$$ which contains all the characters in $$T$$, in order. (Assume the length of $$T$$ is bounded, so it doesn't need to be considered for determining time complexity.)

Here are some examples:

• $$S$$ = "abcabc", $$T$$ = "abc", $$l = 3$$, "[abc]abc".
• $$S$$ = "abcabc", $$T$$ = "acb", $$l = 5$$, "[abcab]c".
• $$S$$ = "ben thinks bananas are the best", $$T$$ = "bans", $$l=7$$, "ben thinks [bananas] are the best"

I found a solution to this using recursion which I believe is $$O(n^2)$$.

def ordered_moving_window(S, T, include_prefix=False):
# Recursion base case
if len(T) == 0:
return 0

shortest_length = float("inf")

for i in range(len(S)):
if S[i] == T:
# Recursively find all the other chars in the string
length = ordered_moving_window(S[i+1:], T[1:], include_prefix=True) + 1

# If this is being called recursively, then we need to include
# all the characters before the first character we found
# in our length calculation
if include_prefix:
length += i

shortest_length = min(length, shortest_length)

return shortest_length

print(ordered_moving_window("abcabc", "abc")) # 3
print(ordered_moving_window("abcabc", "acb")) # 5
print(ordered_moving_window("ben thinks bananas are the best", "bans")) # 7


I believe the worst case for this particular solution is something like $$S$$ = "aaaaaaaab", $$T$$ = "ab", where the solution would need to traverse down the list (which is $$O(n)$$) for each "a" in $$S$$ (of which there are $$n$$), leading to a total time complexity of $$O(n^2)$$.

A few years ago, my professor assigned me a version of this problem, and I submitted this $$O(n^2)$$ solution. In my solution writeup, I also mentioned that I didn't believe an $$O(n)$$ solution was possible. My justification was similar to:

Consider a hypothetical $$O(n)$$ algorithm where $$T$$ = "abc". For $$S$$ = "ababc", the algorithm would need to ignore the first "ab", identify the solution "ab[abc]", and return $$l = 3$$. However, for $$S$$ = "abac", the algorithm would need to consider the first "ab" to identify the solution "[abac]" and return $$l = 4$$. Since the algorithm cannot look ahead to figure out whether it should consider or ignore a certain character, it cannot make this decision, and therefore such an algorithm cannot exist.

However, my professor disagreed with me, stating that an $$O(n)$$ solution to this problem is possible.

Since then, I've learned of the non-ordered minimum window substring problem, which is similar to the problem I listed earlier, but without the requirement that the characters be in order:

• $$S$$ = "abcabc", $$T$$ = "acb", $$l=3$$, "[abc]abc"
• $$S$$ = "ben thinks bananas are the best", $$T$$ = "bans", $$l = 5$$, "ben think[s ban]anas are the best"

This can be solved in $$O(n)$$ time complexity by keeping pointers to the start and end of the window, using a map to keep track of the characters in the window, advancing the end pointer when the sequence is not valid, and advancing the start pointer when the sequence is valid:

def moving_window_substring(S, T):
# Build a table of the count of each character in T
# (i.e., the chars we need our window to have)
needed_chars = {}
for char in T:
if char in needed_chars:
needed_chars[char] += 1
else:
needed_chars[char] = 1

# Set up the window
start = 0
end = 0
shortest_length = float("inf")
needed_chars_count = len(T)

# Grow the window until we have all the chars we need
while end < len(S):
end_char = S[end]

if end_char in needed_chars:
# If we needed this character, decrement the number of chars we need
needed_chars[end_char] -= 1
if needed_chars[end_char] >= 0:
needed_chars_count -= 1

if needed_chars_count == 0:
# The window is valid, we have all the chars we need
# Start shortening the window until it is no longer valid
while True:
start_char = S[start]

if start_char in needed_chars:
if needed_chars[start_char] < 0:
needed_chars[start_char] += 1
else:
# We need this character, break out of the loop
break

start += 1

shortest_length = min(shortest_length, end - start + 1)

end += 1

return shortest_length

print(moving_window_substring("abcabc", "abc")) # 3
print(moving_window_substring("abcabc", "acb")) # 3
print(moving_window_substring("ben thinks bananas are the best", "bans")) # 5
print(moving_window_substring("ben thinks bananas are the bans", "bans")) # 4


Is there a similar $$O(n)$$-time-complexity solution to the ordered version of the problem?

• I just realised you restrict T to constant length, so any algorithm that takes $O(|S||T|)$ time would work. The standard Needleman-Wunsch global alignment algorithm, which has this time complexity, could be easily modified to work. Mar 7 at 13:00

Yes, if the length of T can be considered as a constant.

Here is an efficient algorithm.

def shortest_super_subsequence(S, T):
if len(T) == 0: return 0
shortest_length = float("inf")

indices = [-1] * len(T)
while True:
for i in range(0, len(T)):
if i == 0:
indices = S.find(T, indices + 1)
else:
indices[i] = S.find(T[i], max(indices[i - 1] + 1, indices[i]))
if indices[i] == -1:
return shortest_length
shortest_length = min(shortest_length,
indices[-1] - indices + 1)


The algorithm above uses indices[i] to track the position of T[i] found in each search of a subsequence that contains T. Each time we will move to right by one position to search for T. For other character T[i], we will start search at the later position of its current position and one position later than the current position of T[i-1].

Let len(S) be $$n$$. The algorithm above runs in time $$O(n)$$ if the length of T is considered as a constant. If len(T) is denoted by variable $$m$$, it runs in time $$O(nm)$$, since all updates on indices[j] need $$O(n)$$ time for each j. The worst case happens in situations like S="abdabdabdabdabdabdabdc" and T="abababc".

The algorithm can be speed-up by breaking the inner loop if indices[j] stays the same. Although significant, this improvement does not change the asymptotic time-complexity.

The algorithm can be thought as sliding a window (of varying size) from index indices to indices[-1].

• "if the length of T can be considered as a constant." should have been "if the length of T is bounded by a constant." Mar 7 at 12:37
• Ah, using max(indices[i - 1] + 1, indices[i]) instead of just indices[i - 1] + 1 is what enables the total work done updating each indices[j] to be $O(n)$ time -- the leftmost valid position of T[j] will never slide left as we move the starting position to the right, so we can safely start searching for it from where we left off last time. Mar 7 at 13:16