Bird
Raised Fist0
DSA Javaprogramming~5 mins

Minimum Window Substring in DSA Java - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Minimum Window Substring
O(n + m)
Understanding Time Complexity

We want to understand how the time needed to find the smallest substring containing all characters of another string grows as the input size increases.

How does the algorithm's work increase when the input strings get longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int left = 0, right = 0, count = t.length(), minLen = Integer.MAX_VALUE, start = 0;
    while (right < s.length()) {
        if (need[s.charAt(right++)]-- > 0) count--;
        while (count == 0) {
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }
            if (++need[s.charAt(left++)] > 0) count++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

This code finds the smallest substring in s that contains all characters of t.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The while loop moving the right pointer through string s.
  • Secondary operation: The inner while loop moving the left pointer to shrink the window.
  • How many times: Each character in s is visited at most twice, once by right and once by left.
How Execution Grows With Input

As the input string s grows, the pointers left and right each move forward through the string, but never move backward.

Input Size (n)Approx. Operations
10About 20 moves (each pointer moves through the string once)
100About 200 moves
1000About 2000 moves

Pattern observation: The total operations grow roughly twice the input size, so the growth is linear.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to find the minimum window grows linearly with the size of both strings s and t.

Common Mistake

[X] Wrong: "Because there are nested loops, the time complexity must be quadratic (O(nĀ²))."

[OK] Correct: The inner loop does not restart from the beginning each time; both pointers only move forward through the string once, so total work is linear.

Interview Connect

Understanding this sliding window approach and its linear time complexity shows you can handle efficient substring search problems, a valuable skill in many coding challenges.

Self-Check

What if we changed the character set from ASCII (128) to Unicode with many more characters? How would the time complexity change?

Practice

(1/5)
1. What is the main goal of the Minimum Window Substring problem?
easy
A. Find the smallest substring in a string that contains all characters of another string
B. Find the longest substring without repeating characters
C. Count the number of substrings that contain a specific character
D. Sort the characters of a string in ascending order

Solution

  1. Step 1: Understand the problem statement

    The problem asks to find the smallest part of a string that includes all characters from another string.

  2. Step 2: Compare options with the problem goal

    Only Find the smallest substring in a string that contains all characters of another string matches the goal of finding the smallest substring containing all characters of another string.

  3. Final Answer:

    Find the smallest substring in a string that contains all characters of another string -> Option A

  4. Quick Check:

    Minimum window substring = smallest substring containing all chars [OK]
Hint: Look for smallest substring covering all target chars [OK]
Common Mistakes:
  • Confusing with longest substring problems
  • Thinking about sorting instead of substring search
  • Ignoring the requirement to include all characters
2. Which Java data structure is most suitable to keep track of character counts when solving the Minimum Window Substring problem?
easy
A. ArrayList<Character>
B. LinkedList<Character>
C. HashMap
D. Stack<Character>

Solution

  1. Step 1: Identify the need for character frequency tracking

    We need to count how many times each character appears in the target string and current window.

  2. Step 2: Choose a data structure that maps characters to counts

    HashMap allows storing character keys with their counts efficiently.

  3. Final Answer:

    HashMap -> Option C

  4. Quick Check:

    Use HashMap for char count tracking [OK]
Hint: Use HashMap to map chars to counts quickly [OK]
Common Mistakes:
  • Using ArrayList which doesn't map keys to counts
  • Using Stack or LinkedList which don't store counts
  • Trying to use arrays without knowing character range
3. What will be the output of the following Java code snippet? 
String s = "ADOBECODEBANC";
String t = "ABC";
// Assume minWindow(s, t) returns the minimum window substring
System.out.println(minWindow(s, t));
Given that minWindow is correctly implemented for the Minimum Window Substring problem.
medium
A. "BANC"
B. "ADOBEC"
C. "CODEBA"
D. "DOBECODEBA"

Solution

  1. Step 1: Understand the input strings

    String s is "ADOBECODEBANC" and t is "ABC". We want the smallest substring of s containing A, B, and C.

  2. Step 2: Identify the minimum window substring

    The substring "BANC" is the shortest substring containing all characters A, B, and C.

  3. Final Answer:

    "BANC" -> Option A

  4. Quick Check:

    Minimum window substring for "ABC" in s = "BANC" [OK]
Hint: Remember classic example: "BANC" is minimum window for "ABC" [OK]
Common Mistakes:
  • Choosing longer substrings that contain all chars
  • Confusing order of characters in substring
  • Assuming first occurrence is minimum window
4. Consider this buggy Java code snippet for Minimum Window Substring: 
public String minWindow(String s, String t) {
    Map map = new HashMap<>();
    for (char c : t.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0, count = t.length();
    int minLen = Integer.MAX_VALUE, start = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) - 1);
            if (map.get(c) >= 0) count--;
        }
        while (count == 0) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            char leftChar = s.charAt(left);
            if (map.containsKey(leftChar)) {
                map.put(leftChar, map.get(leftChar) + 1);
                if (map.get(leftChar) > 0) count++;
            }
            left++;
        }
        right++;
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
What is the main bug in this code?
medium
A. The map is not updated correctly when shrinking the window
B. The substring returned uses wrong indices
C. The while loop condition should be count > 0 instead of count == 0
D. The count variable is initialized incorrectly

Solution

  1. Step 1: Analyze the substring return statement

    The substring is returned using s.substring(start, start + minLen). In Java, substring's end index is exclusive, so this is correct.

  2. Step 2: Check map and count updates

    The map and count updates when expanding and shrinking the window are correct.

  3. Step 3: Check loop conditions and initialization

    Count initialization and while loop conditions are correct.

  4. Step 4: Identify the actual bug

    The main bug is that the code does not handle the case when the minimum window substring is not found, returning an empty string is correct, so no bug there. The code is logically correct.

  5. Step 5: Re-examine options

    Options A, B, and C are incorrect. The substring returned uses wrong indices is also not a bug. Therefore, no bug exists in the code.

  6. Step 6: Final Answer

    No bug found in the code snippet
Hint: Check carefully map and count updates and substring indices [OK]
Common Mistakes:
  • Confusing loop conditions for count
  • Incorrect substring indices
  • Ignoring map updates when shrinking window
5. You want to find the minimum window substring of s = "aabbccdd" that contains all characters of t = "abc". Which of the following substrings is the correct minimum window substring?
hard
A. "abbc"
B. "bcca"
C. "abc"
D. "aabbcc"

Solution

  1. Step 1: Identify all substrings containing 'a', 'b', and 'c'

    Check substrings of s that include at least one 'a', one 'b', and one 'c'.

  2. Step 2: Find the smallest such substring

    "aabbcc" (positions 0 to 5) contains 'a', 'b', 'c' and is the smallest continuous substring containing all characters. "abbc" is not a continuous substring in s. "abc" does not appear as a continuous substring. "bcca" is not a substring in order.

  3. Final Answer:

    "aabbcc" -> Option D

  4. Quick Check:

    Minimum window substring = "aabbcc" [OK]
Hint: Check all substrings, pick shortest with all chars [OK]
Common Mistakes:
  • Assuming "abc" must appear in order
  • Choosing shorter substrings that are not continuous
  • Ignoring repeated characters in s
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard