DSA-025 · Multiplicity deficits with grow-then-shrink coverage

Minimum Window Substring

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 14568 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the shortest contiguous source substring containing every target occurrence, including repeated required characters.

source and target are non-null ASCII strings of 0–100,000 code units, each code unit in 0..127. Matching is case-sensitive; whitespace, punctuation, and NUL are ordinary symbols. Non-ASCII inputs are outside this 128-slot contract.
A window covers target when each symbol occurs at least as often as in target. Return the shortest covering substring; among equal minimum lengths choose the earliest start. Return "" for an empty target or when no covering window exists.
Preserve both strings. Store candidate boundaries and allocate only the final substring. missing counts required occurrences still absent, not the number of distinct symbols ever encountered.

Examples

Input: source="ADOBECODEBANC", target="ABC"
Output: "BANC"
BANC covers A,B,C in length four; target order is not required.
Input: source="AAABBC", target="AABC"
Output: "AABBC"
Two A occurrences are necessary, so ABC alone would not cover the target.

Before you start

Contiguous windows, inclusive bounds, and empty intervals
Java frequency arrays and loop-invariant reasoning

Recognize the structure

Coverage survives adding source symbols, while removing a required occurrence can break it. Grow until all required occurrences are present, then shrink through surplus symbols to find the best covered suffix for this right endpoint.

Try before revealing

Hint 1

Which target occurrences are still missing from the current window?

Hint 2

How do negative deficits represent surplus copies?

Hint 3

Grow until missing is zero; record and shrink while coverage survives.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate starts and test coverage

For every left, grow right with fresh counts until all 128 requirements are covered. For AABC and target ABC, left 0 first covers at right 3 with AABC; left 1 first covers with ABC and improves the answer. Stop each start at its first cover because longer windows at the same start cannot improve its length. This O(128n²+m) baseline keeps the earliest start on equal lengths.

Improve the baseline

Signed deficits encode surplus

Set deficit[c]=targetCount[c]-windowCount[c]. Positive means missing, zero means exactly met, and negative means surplus. missing is the sum of positive deficits, initialized to target.length().

Grow and reduce missing only when useful

Before decrementing the entered slot, a positive value means this occurrence fills a required deficit. Only then decrement missing; irrelevant and surplus symbols do not change coverage.

Shrink every covered candidate

While missing==0, consider the window for the best answer, then increment the outgoing slot. If it becomes positive, a required occurrence was lost and missing increases. Continue expansion only after coverage breaks.

Why it is correct

Deficit invariant

For every symbol deficit equals target count minus current-window count, and missing equals the sum of max(deficit[c],0). The zero-crossing updates preserve this identity on both entry and removal.

Minimal candidates and discarded starts

For a fixed right, the shrink loop evaluates every still-available covered start through the last feasible one. A removed start already yielded a covering window ending no later than this right; any future window with that same start is longer and cannot improve it. Discarding it loses no global optimum.

Optimality, ties, and termination

Every potentially improving covering window is considered before its start is discarded. Update only for strictly smaller length; right endpoints increase, so any later equal-length candidate has a later start and cannot replace the earliest one. Each pointer advances at most n times; the final boundaries give the required optimum or absence.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    public static String minWindow(String source, String target) {
        if (target.isEmpty()) return "";
        int[] deficit = new int[128];
        for (int i = 0; i < target.length(); i++) deficit[target.charAt(i)]++;
        int missing = target.length(), left = 0, bestStart = 0, bestLength = Integer.MAX_VALUE;
        for (int right = 0; right < source.length(); right++) {
            if (deficit[source.charAt(right)]-- > 0) missing--;
            while (missing == 0) {
                if (right - left + 1 < bestLength) { bestStart = left; bestLength = right - left + 1; }
                if (++deficit[source.charAt(left++)] > 0) missing++;
            }
        }
        return bestLength == Integer.MAX_VALUE ? "" : source.substring(bestStart, bestStart + bestLength);
    }
    public static String baseline(String source, String target) {
        if (target.isEmpty()) return "";
        int[] required = new int[128];
        for (int i = 0; i < target.length(); i++) required[target.charAt(i)]++;
        int bestStart = 0, bestLength = Integer.MAX_VALUE;
        for (int left = 0; left < source.length(); left++) {
            int[] have = new int[128];
            for (int right = left; right < source.length(); right++) {
                have[source.charAt(right)]++;
                boolean covered = true;
                for (int c = 0; c < 128; c++) if (have[c] < required[c]) covered = false;
                if (covered) {
                    if (right - left + 1 < bestLength) { bestStart = left; bestLength = right - left + 1; }
                    break;
                }
            }
        }
        return bestLength == Integer.MAX_VALUE ? "" : source.substring(bestStart, bestStart + bestLength);
    }
}

Read the meaningful blocks

Postdecrement on entry

The old deficit decides whether the entering occurrence was required; testing the new value with the same comparison would mishandle the final missing copy.

Preincrement on exit

The new positive deficit means coverage just broke. A transition from -1 to 0 merely removes surplus and stays covered.

Save indices, then substring once

Avoid allocating every candidate. Return "" if bestLength was never improved; it also represents the explicit empty-target policy.

Complexity

O(n+m+128) time and O(128) auxiliary state, excluding the returned substring. The nested shrink loop is amortized linear because left never retreats.

The baseline costs O(128n²+m) time and O(128) state. Only the final substring is allocated in each implementation; its storage is O(answer length), rather than O(1) total space.

Exact-state walkthroughs

Reveal normal and boundary traces

Cover, shrink, and improve the best boundaries

Input: {"source":"ADOBECODEBANC","target":"ABC"} · Result: "BANC"

Step 1 of 35: Initialize every required occurrence as missing.

Positive deficits are missing occurrences; zero slots are omitted from the display and negative slots will mean surplus.

Original text — highlighted retained interval

0: "A"
1: "D"
2: "O"
3: "B"
4: "E"
5: "C"
6: "O"
7: "D"
8: "E"
9: "B"
10: "A"
11: "N"
12: "C"

Nonzero deficits — positive missing, negative surplus

"A": 1
"B": 1
"C": 1

State after this step
Variable	Value
text	`"ADOBECODEBANC"`
left	`0`
right	`-1`
window	`""`
deficits	`[["A",1],["B",1],["C",1]]`
missing	`3`
bestStart	`0`
bestLength	`null`

See the affected Java block

 1 public final class Solution {
 2     public static String minWindow(String source, String target) {
 3         if (target.isEmpty()) return "";
 4         int[] deficit = new int[128];
 5         for (int i = 0; i < target.length(); i++) deficit[target.charAt(i)]++;
 6         int missing = target.length(), left = 0, bestStart = 0, bestLength = Integer.MAX_VALUE;
 7         for (int right = 0; right < source.length(); right++) {
 8             if (deficit[source.charAt(right)]-- > 0) missing--;
 9             while (missing == 0) {
10                 if (right - left + 1 < bestLength) { bestStart = left; bestLength = right - left + 1; }
11                 if (++deficit[source.charAt(left++)] > 0) missing++;
12             }
13         }
14         return bestLength == Integer.MAX_VALUE ? "" : source.substring(bestStart, bestStart + bestLength);
15     }
16     public static String baseline(String source, String target) {
17         if (target.isEmpty()) return "";
18         int[] required = new int[128];
19         for (int i = 0; i < target.length(); i++) required[target.charAt(i)]++;
20         int bestStart = 0, bestLength = Integer.MAX_VALUE;
21         for (int left = 0; left < source.length(); left++) {
22             int[] have = new int[128];
23             for (int right = left; right < source.length(); right++) {
24                 have[source.charAt(right)]++;
25                 boolean covered = true;
26                 for (int c = 0; c < 128; c++) if (have[c] < required[c]) covered = false;
27                 if (covered) {
28                     if (right - left + 1 < bestLength) { bestStart = left; bestLength = right - left + 1; }
29                     break;
30                 }
31             }
32         }
33         return bestLength == Integer.MAX_VALUE ? "" : source.substring(bestStart, bestStart + bestLength);
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize every required occurrence as missing.
Positive deficits are missing occurrences; zero slots are omitted from the display and negative slots will mean surplus.
text
"ADOBECODEBANC"
left
0
right
-1
window
""
deficits
[["A",1],["B",1],["C",1]]
missing
3
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
0
right
0
window
"A"
deficits
[["B",1],["C",1]]
missing
2
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
0
right
1
window
"AD"
deficits
[["B",1],["C",1],["D",-1]]
missing
2
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
0
right
2
window
"ADO"
deficits
[["B",1],["C",1],["D",-1],["O",-1]]
missing
2
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
0
right
3
window
"ADOB"
deficits
[["C",1],["D",-1],["O",-1]]
missing
1
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
0
right
4
window
"ADOBE"
deficits
[["C",1],["D",-1],["E",-1],["O",-1]]
missing
1
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
0
right
5
window
"ADOBEC"
deficits
[["D",-1],["E",-1],["O",-1]]
missing
0
bestStart
0
bestLength
null
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
0
right
5
window
"ADOBEC"
deficits
[["D",-1],["E",-1],["O",-1]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
1
right
5
window
"DOBEC"
deficits
[["A",1],["D",-1],["E",-1],["O",-1]]
missing
1
bestStart
0
bestLength
6
outgoing
"A"
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
1
right
6
window
"DOBECO"
deficits
[["A",1],["D",-1],["E",-1],["O",-2]]
missing
1
bestStart
0
bestLength
6
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
1
right
7
window
"DOBECOD"
deficits
[["A",1],["D",-2],["E",-1],["O",-2]]
missing
1
bestStart
0
bestLength
6
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
1
right
8
window
"DOBECODE"
deficits
[["A",1],["D",-2],["E",-2],["O",-2]]
missing
1
bestStart
0
bestLength
6
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
1
right
9
window
"DOBECODEB"
deficits
[["A",1],["B",-1],["D",-2],["E",-2],["O",-2]]
missing
1
bestStart
0
bestLength
6
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
1
right
10
window
"DOBECODEBA"
deficits
[["B",-1],["D",-2],["E",-2],["O",-2]]
missing
0
bestStart
0
bestLength
6
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
1
right
10
window
"DOBECODEBA"
deficits
[["B",-1],["D",-2],["E",-2],["O",-2]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
2
right
10
window
"OBECODEBA"
deficits
[["B",-1],["D",-1],["E",-2],["O",-2]]
missing
0
bestStart
0
bestLength
6
outgoing
"D"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
2
right
10
window
"OBECODEBA"
deficits
[["B",-1],["D",-1],["E",-2],["O",-2]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
3
right
10
window
"BECODEBA"
deficits
[["B",-1],["D",-1],["E",-2],["O",-1]]
missing
0
bestStart
0
bestLength
6
outgoing
"O"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
3
right
10
window
"BECODEBA"
deficits
[["B",-1],["D",-1],["E",-2],["O",-1]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
4
right
10
window
"ECODEBA"
deficits
[["D",-1],["E",-2],["O",-1]]
missing
0
bestStart
0
bestLength
6
outgoing
"B"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
4
right
10
window
"ECODEBA"
deficits
[["D",-1],["E",-2],["O",-1]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
5
right
10
window
"CODEBA"
deficits
[["D",-1],["E",-1],["O",-1]]
missing
0
bestStart
0
bestLength
6
outgoing
"E"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
5
right
10
window
"CODEBA"
deficits
[["D",-1],["E",-1],["O",-1]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
6
right
10
window
"ODEBA"
deficits
[["C",1],["D",-1],["E",-1],["O",-1]]
missing
1
bestStart
0
bestLength
6
outgoing
"C"
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
6
right
11
window
"ODEBAN"
deficits
[["C",1],["D",-1],["E",-1],["N",-1],["O",-1]]
missing
1
bestStart
0
bestLength
6
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"ADOBECODEBANC"
left
6
right
12
window
"ODEBANC"
deficits
[["D",-1],["E",-1],["N",-1],["O",-1]]
missing
0
bestStart
0
bestLength
6
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
6
right
12
window
"ODEBANC"
deficits
[["D",-1],["E",-1],["N",-1],["O",-1]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
7
right
12
window
"DEBANC"
deficits
[["D",-1],["E",-1],["N",-1]]
missing
0
bestStart
0
bestLength
6
outgoing
"O"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
7
right
12
window
"DEBANC"
deficits
[["D",-1],["E",-1],["N",-1]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
8
right
12
window
"EBANC"
deficits
[["E",-1],["N",-1]]
missing
0
bestStart
0
bestLength
6
outgoing
"D"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
8
right
12
window
"EBANC"
deficits
[["E",-1],["N",-1]]
missing
0
bestStart
8
bestLength
5
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
9
right
12
window
"BANC"
deficits
[["N",-1]]
missing
0
bestStart
8
bestLength
5
outgoing
"E"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"ADOBECODEBANC"
left
9
right
12
window
"BANC"
deficits
[["N",-1]]
missing
0
bestStart
9
bestLength
4
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"ADOBECODEBANC"
left
10
right
12
window
"ANC"
deficits
[["B",1],["N",-1]]
missing
1
bestStart
9
bestLength
4
outgoing
"B"
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
"BANC"

Repeated requirements and surplus

Input: {"source":"AAABBC","target":"AABC"} · Result: "AABBC"

Step 1 of 12: Initialize every required occurrence as missing.

Positive deficits are missing occurrences; zero slots are omitted from the display and negative slots will mean surplus.

Original text — highlighted retained interval

0: "A"
1: "A"
2: "A"
3: "B"
4: "B"
5: "C"

Nonzero deficits — positive missing, negative surplus

"A": 2
"B": 1
"C": 1

State after this step
Variable	Value
text	`"AAABBC"`
left	`0`
right	`-1`
window	`""`
deficits	`[["A",2],["B",1],["C",1]]`
missing	`4`
bestStart	`0`
bestLength	`null`

See the affected Java block

 1 public final class Solution {
 2     public static String minWindow(String source, String target) {
 3         if (target.isEmpty()) return "";
 4         int[] deficit = new int[128];
 5         for (int i = 0; i < target.length(); i++) deficit[target.charAt(i)]++;
 6         int missing = target.length(), left = 0, bestStart = 0, bestLength = Integer.MAX_VALUE;
 7         for (int right = 0; right < source.length(); right++) {
 8             if (deficit[source.charAt(right)]-- > 0) missing--;
 9             while (missing == 0) {
10                 if (right - left + 1 < bestLength) { bestStart = left; bestLength = right - left + 1; }
11                 if (++deficit[source.charAt(left++)] > 0) missing++;
12             }
13         }
14         return bestLength == Integer.MAX_VALUE ? "" : source.substring(bestStart, bestStart + bestLength);
15     }
16     public static String baseline(String source, String target) {
17         if (target.isEmpty()) return "";
18         int[] required = new int[128];
19         for (int i = 0; i < target.length(); i++) required[target.charAt(i)]++;
20         int bestStart = 0, bestLength = Integer.MAX_VALUE;
21         for (int left = 0; left < source.length(); left++) {
22             int[] have = new int[128];
23             for (int right = left; right < source.length(); right++) {
24                 have[source.charAt(right)]++;
25                 boolean covered = true;
26                 for (int c = 0; c < 128; c++) if (have[c] < required[c]) covered = false;
27                 if (covered) {
28                     if (right - left + 1 < bestLength) { bestStart = left; bestLength = right - left + 1; }
29                     break;
30                 }
31             }
32         }
33         return bestLength == Integer.MAX_VALUE ? "" : source.substring(bestStart, bestStart + bestLength);
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize every required occurrence as missing.
Positive deficits are missing occurrences; zero slots are omitted from the display and negative slots will mean surplus.
text
"AAABBC"
left
0
right
-1
window
""
deficits
[["A",2],["B",1],["C",1]]
missing
4
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"AAABBC"
left
0
right
0
window
"A"
deficits
[["A",1],["B",1],["C",1]]
missing
3
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"AAABBC"
left
0
right
1
window
"AA"
deficits
[["B",1],["C",1]]
missing
2
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"AAABBC"
left
0
right
2
window
"AAA"
deficits
[["A",-1],["B",1],["C",1]]
missing
2
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"AAABBC"
left
0
right
3
window
"AAAB"
deficits
[["A",-1],["C",1]]
missing
1
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"AAABBC"
left
0
right
4
window
"AAABB"
deficits
[["A",-1],["B",-1],["C",1]]
missing
1
bestStart
0
bestLength
null
Enter a source symbol and fill a deficit only when needed.
missing equals the sum of positive deficits, not the number of target symbols seen.
text
"AAABBC"
left
0
right
5
window
"AAABBC"
deficits
[["A",-1],["B",-1]]
missing
0
bestStart
0
bestLength
null
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"AAABBC"
left
0
right
5
window
"AAABBC"
deficits
[["A",-1],["B",-1]]
missing
0
bestStart
0
bestLength
6
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"AAABBC"
left
1
right
5
window
"AABBC"
deficits
[["B",-1]]
missing
0
bestStart
0
bestLength
6
outgoing
"A"
Consider this covered window before removing its left symbol.
All required occurrences are covered. Only a strictly shorter candidate replaces the earlier tie.
text
"AAABBC"
left
1
right
5
window
"AABBC"
deficits
[["B",-1]]
missing
0
bestStart
1
bestLength
5
Remove the left symbol and inspect the new deficit.
A new positive deficit breaks coverage; removing surplus up to zero keeps coverage. The discarded start cannot improve with a later endpoint.
text
"AAABBC"
left
2
right
5
window
"ABBC"
deficits
[["A",1],["B",-1]]
missing
1
bestStart
1
bestLength
5
outgoing
"A"
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
"AABBC"

Test the contract

Input: source="abc", target=""
Output: ""
Explicit empty target.
Input: source="A", target="AA"
Output: ""
Insufficient multiplicity.
Input: source="ABBA", target="AB"
Output: "AB"
Earliest tie wins over BA.
Input: source="aA", target="A"
Output: "A"
Case-sensitive ASCII matching.

Common mistakes and counterexamples

Track a set of seen target symbols

Counterexample: source AB with target AAB sees A and B but lacks one A.

Track multiplicity deficits or exact satisfied requirements.

Break coverage when surplus reaches zero

Counterexample: For source AABC,target ABC, removing the first A leaves ABC still covered.

Coverage breaks only when the outgoing deficit becomes positive.

Overwrite equal-length answers

Counterexample: source ABBA,target AB has AB first and BA later.

Update only on strictly shorter candidates to retain the earliest tie.

Follow-ups

Return all minimum windows.

First determine the minimum length, then enumerate covering windows of exactly that length in source order. Define whether duplicate text at different starts is distinct and count output storage.

Process a stream with bounded memory.

Irrelevant history can sometimes be discarded, but returning actual substring text requires retaining or externally storing the candidate range. Frequency counts alone cannot reconstruct characters after the stream has passed.

Support Unicode.

Choose code points or grapheme clusters and define normalization and index boundaries. Maps can handle a variable alphabet, but String.substring still takes UTF-16 offsets; preserve a mapping if scanning code points.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 104/20,000 characters

Self-review

I define deficits and missing occurrences exactly.I explain both zero-crossing directions.I prove discarded starts cannot improve later.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Sliding windows: define validity first

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.