DSA-023 · Fixed-length frequency differences

Permutation in String

Intermediate · Java 21 · Version 1 · editorial draft

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

Understand the problem

Determine whether text contains a contiguous substring that is a permutation of pattern.

pattern and text are non-null lowercase ASCII a–z strings, each 0–100,000 characters. Multiplicity matters: a permutation rearranges all occurrences, not just the set of letters.
Return true if any length-pattern.length() window has exactly the pattern frequencies. An empty pattern returns true at boundary zero, including when text is empty. A longer pattern returns false.
Preserve both strings. Indices, lengths, and 26-slot differences use the declared ASCII alphabet; this method does not normalize case or process Unicode symbols.

Examples

Input: pattern="ab", text="eidbaooo"
Output: true
The window ba is a permutation of ab.
Input: pattern="aab", text="abab"
Output: true
The first window aba contains two a occurrences and one b.

Before you start

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

Recognize the structure

A permutation preserves the full frequency vector and length. Scan exactly one pattern-sized window per position; incremental differences avoid rebuilding and sorting every candidate.

Try before revealing

Hint 1

What information survives a permutation?

Hint 2

Keep pattern counts minus current-window counts.

Hint 3

Track nonzero slots and test only after reaching exactly the pattern length.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Sort each candidate window

Sort pattern once. For each legal start, sort its length-m substring and compare. With pattern ab and text cba, cb sorts to bc and fails, while ba sorts to ab and succeeds. Empty pattern compares two empty arrays at start zero. Repeated sorting costs O(m log(m+1)+w·m log(m+1)) time for w=max(0,n-m+1) nonempty-size candidates, plus O(m) temporary storage.

Improve the baseline

Define the signed difference

Initialize difference[c]=patternCount[c]. Entering a text symbol subtracts one; removing the oldest symbol adds one. The array then means pattern counts minus the retained text-window counts.

Count unequal slots

Maintain unequal, the number of nonzero difference entries. Before changing a slot remove its old nonzero contribution, apply delta, then add its new contribution. Crossing zero in either direction stays exact.

Judge only complete windows

After entering right, evict right-m when present. Test unequal==0 only once right≥m-1. Return true at the first match; otherwise exhaust all starts.

Why it is correct

Difference invariant

After eviction the retained window is text[max(0,right-m+1)..right]. Each slot equals the corresponding pattern multiplicity minus this window’s multiplicity, and unequal equals the number of nonzero slots.

Equivalence

For a complete length-m window, unequal==0 is exactly equality of all 26 multiplicities, which is exactly permutation equivalence. Before reaching m positions, no partial window is judged.

Coverage and termination

Every possible length-m start appears once as right-m+1. Early success has a valid matching window; exhausting all starts proves absence. Empty and overlong patterns are resolved explicitly before scanning.

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.

import java.util.Arrays;
public final class Solution {
    private static int adjust(int[] difference, int slot, int delta, int unequal) {
        if (difference[slot] != 0) unequal--;
        difference[slot] += delta;
        if (difference[slot] != 0) unequal++;
        return unequal;
    }
    public static boolean checkInclusion(String pattern, String text) {
        int m = pattern.length();
        if (m == 0) return true;
        if (m > text.length()) return false;
        int[] difference = new int[26]; int unequal = 0;
        for (int i = 0; i < m; i++) unequal = adjust(difference, pattern.charAt(i) - 'a', 1, unequal);
        for (int right = 0; right < text.length(); right++) {
            unequal = adjust(difference, text.charAt(right) - 'a', -1, unequal);
            if (right >= m) unequal = adjust(difference, text.charAt(right - m) - 'a', 1, unequal);
            if (right >= m - 1 && unequal == 0) return true;
        }
        return false;
    }
    public static boolean baseline(String pattern, String text) {
        char[] wanted = pattern.toCharArray(); Arrays.sort(wanted);
        for (int start = 0; start + pattern.length() <= text.length(); start++) {
            char[] candidate = text.substring(start, start + pattern.length()).toCharArray();
            Arrays.sort(candidate);
            if (Arrays.equals(wanted, candidate)) return true;
        }
        return false;
    }
}

Read the meaningful blocks

Two zero-crossing checks

A delta may create a mismatch, remove one, or preserve one. Updating unequal only when a count becomes zero misses the reverse transition.

Evict with the opposite sign

Incoming text subtracts from pattern-minus-window; outgoing text adds back.

Length guard

right≥m-1 ensures the result refers to a full pattern-sized window, not a coincidental partial state.

Complexity

O(n+m+26) worst-case time and O(26) auxiliary space. Each symbol causes a constant number of difference-slot updates; there is no repeated full-window comparison.

The sorted-window baseline takes O(m log(m+1)+w·m log(m+1)) for m>0, plus copying/scanning cost O(wm); the empty-pattern case returns after its first O(1) comparison. It is a small-input baseline, not the intended large-input method.

Exact-state walkthroughs

Reveal normal and boundary traces

Evict and enter until ba matches

Input: {"pattern":"ab","text":"eidbaooo"} · Result: true

Step 1 of 8: Check the explicit empty and overlong pattern policies.

No text window has been judged.

Original text — highlighted retained interval

0: "e"
1: "i"
2: "d"
3: "b"
4: "a"
5: "o"
6: "o"
7: "o"

State after this step
Variable	Value
text	`"eidbaooo"`
pattern	`"ab"`
m	`2`

See the affected Java block

 1 import java.util.Arrays;
 2 public final class Solution {
 3     private static int adjust(int[] difference, int slot, int delta, int unequal) {
 4         if (difference[slot] != 0) unequal--;
 5         difference[slot] += delta;
 6         if (difference[slot] != 0) unequal++;
 7         return unequal;
 8     }
 9     public static boolean checkInclusion(String pattern, String text) {
10         int m = pattern.length();
11         if (m == 0) return true;
12         if (m > text.length()) return false;
13         int[] difference = new int[26]; int unequal = 0;
14         for (int i = 0; i < m; i++) unequal = adjust(difference, pattern.charAt(i) - 'a', 1, unequal);
15         for (int right = 0; right < text.length(); right++) {
16             unequal = adjust(difference, text.charAt(right) - 'a', -1, unequal);
17             if (right >= m) unequal = adjust(difference, text.charAt(right - m) - 'a', 1, unequal);
18             if (right >= m - 1 && unequal == 0) return true;
19         }
20         return false;
21     }
22     public static boolean baseline(String pattern, String text) {
23         char[] wanted = pattern.toCharArray(); Arrays.sort(wanted);
24         for (int start = 0; start + pattern.length() <= text.length(); start++) {
25             char[] candidate = text.substring(start, start + pattern.length()).toCharArray();
26             Arrays.sort(candidate);
27             if (Arrays.equals(wanted, candidate)) return true;
28         }
29         return false;
30     }
31 }
32

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

Read the full static trace

Check the explicit empty and overlong pattern policies.
No text window has been judged.
text
"eidbaooo"
pattern
"ab"
m
2
Initialize pattern-minus-window differences.
The current window is empty, so every difference is its pattern count.
text
"eidbaooo"
left
0
right
-1
window
""
difference
[1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
2
matches
[]
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"eidbaooo"
left
0
right
0
window
"e"
difference
[1,1,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
3
matches
[]
complete
false
matched
false
incoming
"e"
outgoing
null
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"eidbaooo"
left
0
right
1
window
"ei"
difference
[1,1,0,0,-1,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
4
matches
[]
complete
true
matched
false
incoming
"i"
outgoing
null
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"eidbaooo"
left
1
right
2
window
"id"
difference
[1,1,0,-1,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
4
matches
[]
complete
true
matched
false
incoming
"d"
outgoing
"e"
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"eidbaooo"
left
2
right
3
window
"db"
difference
[1,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
2
matches
[]
complete
true
matched
false
incoming
"b"
outgoing
"i"
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"eidbaooo"
left
3
right
4
window
"ba"
difference
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
0
matches
[]
complete
true
matched
true
incoming
"a"
outgoing
"d"
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
true

Repeated symbols require multiplicity

Input: {"pattern":"aab","text":"abb"} · Result: false

Step 1 of 6: Check the explicit empty and overlong pattern policies.

No text window has been judged.

Original text — highlighted retained interval

0: "a"
1: "b"
2: "b"

State after this step
Variable	Value
text	`"abb"`
pattern	`"aab"`
m	`3`

See the affected Java block

 1 import java.util.Arrays;
 2 public final class Solution {
 3     private static int adjust(int[] difference, int slot, int delta, int unequal) {
 4         if (difference[slot] != 0) unequal--;
 5         difference[slot] += delta;
 6         if (difference[slot] != 0) unequal++;
 7         return unequal;
 8     }
 9     public static boolean checkInclusion(String pattern, String text) {
10         int m = pattern.length();
11         if (m == 0) return true;
12         if (m > text.length()) return false;
13         int[] difference = new int[26]; int unequal = 0;
14         for (int i = 0; i < m; i++) unequal = adjust(difference, pattern.charAt(i) - 'a', 1, unequal);
15         for (int right = 0; right < text.length(); right++) {
16             unequal = adjust(difference, text.charAt(right) - 'a', -1, unequal);
17             if (right >= m) unequal = adjust(difference, text.charAt(right - m) - 'a', 1, unequal);
18             if (right >= m - 1 && unequal == 0) return true;
19         }
20         return false;
21     }
22     public static boolean baseline(String pattern, String text) {
23         char[] wanted = pattern.toCharArray(); Arrays.sort(wanted);
24         for (int start = 0; start + pattern.length() <= text.length(); start++) {
25             char[] candidate = text.substring(start, start + pattern.length()).toCharArray();
26             Arrays.sort(candidate);
27             if (Arrays.equals(wanted, candidate)) return true;
28         }
29         return false;
30     }
31 }
32

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

Read the full static trace

Check the explicit empty and overlong pattern policies.
No text window has been judged.
text
"abb"
pattern
"aab"
m
3
Initialize pattern-minus-window differences.
The current window is empty, so every difference is its pattern count.
text
"abb"
left
0
right
-1
window
""
difference
[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
2
matches
[]
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"abb"
left
0
right
0
window
"a"
difference
[1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
2
matches
[]
complete
false
matched
false
incoming
"a"
outgoing
null
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"abb"
left
0
right
1
window
"ab"
difference
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
1
matches
[]
complete
false
matched
false
incoming
"b"
outgoing
null
Enter the next symbol, evict if needed, and judge only a complete window.
Each difference equals pattern multiplicity minus retained-window multiplicity. unequal counts exactly the nonzero slots; overlap does not skip a start.
text
"abb"
left
0
right
2
window
"abb"
difference
[1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
unequal
2
matches
[]
complete
true
matched
false
incoming
"b"
outgoing
null
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
false

Test the contract

Input: pattern="", text="abc"
Output: true
The empty permutation occurs at boundary zero.
Input: pattern="abcd", text="abc"
Output: false
Pattern longer than text.
Input: pattern="aab", text="abb"
Output: false
Same letter set is insufficient.
Input: pattern="ab", text="eidboaoo"
Output: false
Both letters appear, but no matching contiguous window.

Common mistakes and counterexamples

Compare only distinct letters

Counterexample: pattern aab and candidate abb have the same set but different counts.

Track multiplicities.

Evict with another subtraction

Counterexample: For pattern ab and text aba, the outgoing a must undo its earlier subtraction.

Add one for the outgoing symbol.

Forget empty-pattern policy

Counterexample: m=0 makes normal fixed-window bounds awkward and can read incorrect positions.

Return true explicitly for the empty pattern.

Follow-ups

Report all starts.

Replace early return with an output list, keep scanning one position at a time, and include overlapping matches. The next lesson implements this variant.

Process a stream.

Keep the most recent m symbols in a ring buffer so the outgoing symbol is available. Frequency state is O(26), but a non-rewindable stream additionally needs O(m) retention.

Support case-sensitive Unicode.

Choose code units, code points, or graphemes and define index meanings. A code-point stream can use a frequency map, but UTF-16 offsets require separate position tracking.

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 · 109/20,000 characters

Self-review

I state the difference sign.I update unequal on both zero crossings.I handle empty and overlong patterns deliberately.

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.