Space complexity incorrect for Minimum Window Subsequence

[Grubiks]

The solution states that the space complexity will be O(1); however, this is not the case since a string is created to store the result i.e., minSubsequence. Worst case, the space would be O(n) where ‘n’ is the string to search. The solution is also using inefficient string building with the += operator, this means the string is recreated every time a character is appended, causing O(n) time where ‘n’ is the string length. Leveraging a StringBuilder has O(1) append time.

---

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Minimum Window Subsequence - Grokking Coding Interview Patterns in Java

[M.Hamza]

Thank you for reaching out to us with your query. Regarding the space complexity in the “Solution: Minimum Window Subsequence” problem, we do not consider the space acquired by the input and output data structures in the overall space complexity of the solution function. The reason for doing so is that space complexity is used to compare the efficiency of two different solutions to the same problem. The space acquired by the input and output data structures will remain the same, regardless of the solution we use. Hence, it is not considered in the space complexity of the solution function. As for the “Solution: Minimum Window Subsequence” problem, the space acquired by the minSubsequence is to store the output of the function, therefore, it is not included in the space complexity of the solution function.
Regarding your second query, we’ve verified that the solution was using inefficient was of finding a substring. Hence, we’ve fixed our code.

I hope this clarifies your confusion. If you still have any questions, please feel free to ask us.