DSA-024 · FOCUSED PRACTICE
Find All Anagrams in a String
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 7911 deterministic checks. Learner drafts are not executed.
Understand the problem
Return all start indices where a text substring is an anagram of a pattern.
- text and pattern are non-null lowercase ASCII a–z strings, each 0–100,000 characters. Anagrams preserve every character multiplicity.
- Return List<Integer> of zero-based starts in increasing order, including overlapping matches. If pattern is longer than text return an empty list. For an empty pattern, return every boundary 0..text.length(), inclusive.
- Preserve strings. Each returned index names a length-pattern.length() substring; the final boundary text.length() is legal only for the zero-length pattern. Output may contain n+1 entries.
Examples
Input:
text="cbaebabacd", pattern="abc"
Output:[0,6]cba and bac have the required three multiplicities.
Input:
text="aaaa", pattern="aa"
Output:[0,1,2]Overlapping windows are separate valid matches.
Before you start
- Contiguous windows, inclusive bounds, and empty intervals
- Java frequency arrays and loop-invariant reasoning
Recognize the structure
This is the fixed-window permutation predicate applied at every legal start. The added requirement is complete, ordered output; finding a match must not skip overlapping candidates.
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.
No unsaved text changes · 113/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Turn the existence test into a predicate at every complete window.
Hint 2
Do matching windows permit skipping the next start?
Hint 3
Append matching starts and keep moving one position at a time.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Sort every length-m window
Sort the pattern and each candidate substring. For text ababa and pattern ab, windows at 0,1,2,3 sort to ab, so every start is emitted. Advancing by m after a match would lose starts 1 and 3. The baseline pays copying and sorting per window but is easy to compare against an independent multiset oracle.
Improve the baseline
Reuse the frequency predicate
Maintain pattern-minus-window differences and their nonzero-slot count exactly as in permutation existence.
Slide one position
Enter text[right], evict text[right-m] if necessary, then judge the completed window. On a match append right-m+1; do not reset counts or jump ahead.
Separate empty windows
An empty substring exists at n+1 boundaries. Enumerate those directly instead of forcing m=0 through the ordinary entering/eviction loop.
Why it is correct
Exact matching state
After every update the difference vector and unequal count describe the current bounded window. Zero unequal slots at length m proves exact multiplicity equality.
Complete ordered enumeration
Every legal nonempty start corresponds to one right endpoint, visited in ascending order. Appending only on equality emits each match once, preserves increasing order, and includes overlaps.
Empty and absent cases
The explicit empty-pattern branch enumerates all n+1 zero-length windows, including when both strings are empty. The overlong-pattern branch emits none; otherwise exhausting text completes the candidate set.
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.*;
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 List<Integer> findAnagrams(String text, String pattern) {
List<Integer> answer = new ArrayList<>();
int m = pattern.length();
if (m == 0) {
for (int boundary = 0; boundary <= text.length(); boundary++) answer.add(boundary);
return answer;
}
if (m > text.length()) return answer;
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) answer.add(right - m + 1);
}
return answer;
}
public static List<Integer> baseline(String text, String pattern) {
List<Integer> answer = new ArrayList<>();
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)) answer.add(start);
}
return answer;
}
}
Read the meaningful blocks
List output costs space
The frequency array is constant size, but storing every matching index is not. Count output separately.
Keep scanning after a hit
Return belongs after the loop. Early return would implement existence rather than all matches.
Boundaries versus positions
For pattern empty, n is a substring boundary even though it is not an index at which a text character can be read.
Complexity
O(n+m+26+z) time and O(26) other workspace, with O(z) returned storage for z matches. The explicit empty-pattern branch is O(n+1) time/output.
For m>0 the sorted-window baseline uses O(m log(m+1)+w·m log(m+1)+wm) time, O(m) temporary space and O(z) output. Empty-pattern enumeration remains O(n+1).
Exact-state walkthroughs
Reveal normal and boundary traces
Emit both separated matches
Input: {"text":"cbaebabacd","pattern":"abc"} · Result: [0,6]
Step 1 of 13: Check the explicit empty and overlong pattern policies.
No text window has been judged.
- 0: "c"
- 1: "b"
- 2: "a"
- 3: "e"
- 4: "b"
- 5: "a"
- 6: "b"
- 7: "a"
- 8: "c"
- 9: "d"
| Variable | Value |
|---|---|
| text | "cbaebabacd" |
| pattern | "abc" |
| m | 3 |
See the affected Java block
1 import java.util.*; 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 List<Integer> findAnagrams(String text, String pattern) { 10 List<Integer> answer = new ArrayList<>(); 11 int m = pattern.length(); 12 if (m == 0) { 13 for (int boundary = 0; boundary <= text.length(); boundary++) answer.add(boundary); 14 return answer; 15 } 16 if (m > text.length()) return answer; 17 int[] difference = new int[26]; int unequal = 0; 18 for (int i = 0; i < m; i++) unequal = adjust(difference, pattern.charAt(i) - 'a', 1, unequal); 19 for (int right = 0; right < text.length(); right++) { 20 unequal = adjust(difference, text.charAt(right) - 'a', -1, unequal); 21 if (right >= m) unequal = adjust(difference, text.charAt(right - m) - 'a', 1, unequal); 22 if (right >= m - 1 && unequal == 0) answer.add(right - m + 1); 23 } 24 return answer; 25 } 26 public static List<Integer> baseline(String text, String pattern) { 27 List<Integer> answer = new ArrayList<>(); 28 char[] wanted = pattern.toCharArray(); Arrays.sort(wanted); 29 for (int start = 0; start + pattern.length() <= text.length(); start++) { 30 char[] candidate = text.substring(start, start + pattern.length()).toCharArray(); 31 Arrays.sort(candidate); 32 if (Arrays.equals(wanted, candidate)) answer.add(start); 33 } 34 return answer; 35 } 36 } 37
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
"cbaebabacd"- pattern
"abc"- m
3
- Initialize pattern-minus-window differences.
The current window is empty, so every difference is its pattern count.
- text
"cbaebabacd"- left
0- right
-1- window
""- difference
[1,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]- unequal
3- 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
"cbaebabacd"- left
0- right
0- window
"c"- 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
"c"- 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
"cbaebabacd"- left
0- right
1- window
"cb"- 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
"cbaebabacd"- left
0- right
2- window
"cba"- 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
[0]- complete
true- matched
true- 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
"cbaebabacd"- left
1- right
3- window
"bae"- difference
[0,0,1,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]- unequal
2- matches
[0]- complete
true- matched
false- incoming
"e"- outgoing
"c"
- 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
"cbaebabacd"- left
2- right
4- window
"aeb"- difference
[0,0,1,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]- unequal
2- matches
[0]- complete
true- matched
false- incoming
"b"- outgoing
"b"
- 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
"cbaebabacd"- left
3- right
5- window
"eba"- difference
[0,0,1,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]- unequal
2- matches
[0]- complete
true- matched
false- incoming
"a"- outgoing
"a"
- 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
"cbaebabacd"- left
4- right
6- window
"bab"- difference
[0,-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]- unequal
2- matches
[0]- complete
true- matched
false- incoming
"b"- 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
"cbaebabacd"- left
5- right
7- window
"aba"- difference
[-1,0,1,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
[0]- complete
true- matched
false- incoming
"a"- outgoing
"b"
- 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
"cbaebabacd"- left
6- right
8- window
"bac"- 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
[0,6]- complete
true- matched
true- incoming
"c"- outgoing
"a"
- 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
"cbaebabacd"- left
7- right
9- window
"acd"- difference
[0,1,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
[0,6]- complete
true- matched
false- incoming
"d"- outgoing
"b"
- Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
- result
[0,6]
Overlaps remain candidates
Input: {"text":"aaaa","pattern":"aa"} · Result: [0,1,2]
Step 1 of 7: Check the explicit empty and overlong pattern policies.
No text window has been judged.
- 0: "a"
- 1: "a"
- 2: "a"
- 3: "a"
| Variable | Value |
|---|---|
| text | "aaaa" |
| pattern | "aa" |
| m | 2 |
See the affected Java block
1 import java.util.*; 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 List<Integer> findAnagrams(String text, String pattern) { 10 List<Integer> answer = new ArrayList<>(); 11 int m = pattern.length(); 12 if (m == 0) { 13 for (int boundary = 0; boundary <= text.length(); boundary++) answer.add(boundary); 14 return answer; 15 } 16 if (m > text.length()) return answer; 17 int[] difference = new int[26]; int unequal = 0; 18 for (int i = 0; i < m; i++) unequal = adjust(difference, pattern.charAt(i) - 'a', 1, unequal); 19 for (int right = 0; right < text.length(); right++) { 20 unequal = adjust(difference, text.charAt(right) - 'a', -1, unequal); 21 if (right >= m) unequal = adjust(difference, text.charAt(right - m) - 'a', 1, unequal); 22 if (right >= m - 1 && unequal == 0) answer.add(right - m + 1); 23 } 24 return answer; 25 } 26 public static List<Integer> baseline(String text, String pattern) { 27 List<Integer> answer = new ArrayList<>(); 28 char[] wanted = pattern.toCharArray(); Arrays.sort(wanted); 29 for (int start = 0; start + pattern.length() <= text.length(); start++) { 30 char[] candidate = text.substring(start, start + pattern.length()).toCharArray(); 31 Arrays.sort(candidate); 32 if (Arrays.equals(wanted, candidate)) answer.add(start); 33 } 34 return answer; 35 } 36 } 37
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
"aaaa"- pattern
"aa"- m
2
- Initialize pattern-minus-window differences.
The current window is empty, so every difference is its pattern count.
- text
"aaaa"- left
0- right
-1- window
""- difference
[2,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
[]
- 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
"aaaa"- left
0- right
0- window
"a"- 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
"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
"aaaa"- left
0- right
1- window
"aa"- 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
[0]- complete
true- matched
true- 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
"aaaa"- left
1- right
2- window
"aa"- 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
[0,1]- complete
true- matched
true- incoming
"a"- outgoing
"a"
- 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
"aaaa"- left
2- right
3- window
"aa"- 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
[0,1,2]- complete
true- matched
true- incoming
"a"- outgoing
"a"
- Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
- result
[0,1,2]
Empty pattern matches boundaries
Input: {"text":"ab","pattern":""} · Result: [0,1,2]
Step 1 of 5: Check the explicit empty and overlong pattern policies.
No text window has been judged.
- 0: "a"
- 1: "b"
| Variable | Value |
|---|---|
| text | "ab" |
| pattern | "" |
| m | 0 |
See the affected Java block
1 import java.util.*; 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 List<Integer> findAnagrams(String text, String pattern) { 10 List<Integer> answer = new ArrayList<>(); 11 int m = pattern.length(); 12 if (m == 0) { 13 for (int boundary = 0; boundary <= text.length(); boundary++) answer.add(boundary); 14 return answer; 15 } 16 if (m > text.length()) return answer; 17 int[] difference = new int[26]; int unequal = 0; 18 for (int i = 0; i < m; i++) unequal = adjust(difference, pattern.charAt(i) - 'a', 1, unequal); 19 for (int right = 0; right < text.length(); right++) { 20 unequal = adjust(difference, text.charAt(right) - 'a', -1, unequal); 21 if (right >= m) unequal = adjust(difference, text.charAt(right - m) - 'a', 1, unequal); 22 if (right >= m - 1 && unequal == 0) answer.add(right - m + 1); 23 } 24 return answer; 25 } 26 public static List<Integer> baseline(String text, String pattern) { 27 List<Integer> answer = new ArrayList<>(); 28 char[] wanted = pattern.toCharArray(); Arrays.sort(wanted); 29 for (int start = 0; start + pattern.length() <= text.length(); start++) { 30 char[] candidate = text.substring(start, start + pattern.length()).toCharArray(); 31 Arrays.sort(candidate); 32 if (Arrays.equals(wanted, candidate)) answer.add(start); 33 } 34 return answer; 35 } 36 } 37
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
"ab"- pattern
""- m
0
- Emit one empty-substring boundary.
Every boundary from zero through n owns one zero-length substring.
- text
"ab"- boundary
0- matches
[0]
- Emit one empty-substring boundary.
Every boundary from zero through n owns one zero-length substring.
- text
"ab"- boundary
1- matches
[0,1]
- Emit one empty-substring boundary.
Every boundary from zero through n owns one zero-length substring.
- text
"ab"- boundary
2- matches
[0,1,2]
- Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
- result
[0,1,2]
Test the contract
Input:
text="", pattern=""
Output:[0]One empty boundary.
Input:
text="abc", pattern=""
Output:[0,1,2,3]All empty boundaries.
Input:
text="aa", pattern="aaa"
Output:[]No complete window.
Input:
text="abab", pattern="ab"
Output:[0,1,2]Adjacent and overlapping matches.
Common mistakes and counterexamples
Jump past a matched window
Counterexample: aaaa with aa has matches at 0,1,2, not just 0 and 2.
Advance right by one regardless of matches.
Return text.length() for a nonempty pattern
Counterexample: The last complete start is n-m.
Compute right-m+1 only for complete windows.
Use letter presence instead of counts
Counterexample: aab does not match abb.
Maintain the full difference vector.
Follow-ups
Group matched substrings.
All matched substrings share the pattern signature, so grouping them by that signature adds no information. Return starts or source spans to avoid copying O(zm) characters unnecessarily.
Allow wildcard pattern slots.
Track literal multiplicity requirements; wildcard positions absorb the remaining window characters. Exact zero differences are no longer the predicate because surplus letters may be allowed.
Continue across streamed chunks.
Carry counts, global offset, and the last m symbols across boundaries. Resetting on every chunk would miss a match whose substring crosses two chunks.