#567
Permutation in String
Medium Fixed window + counts
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether some rearrangement of s1 appears as a contiguous substring of s2.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does some rearrangement of s1 appear inside s2?
Why this works: a rearrangement has the same letter counts. Slide a window of length |s1| over s2 and compare counts.
Example: s1 = "ab", s2 = "eidbaooo"
"ei", "id", "db" → no"ba" → counts a1 b1 match → true
✦Hints open one at a time
A rearrangement has exactly the same letter counts.
Slide a window of length |s1| over s2 and compare counts.
Track how many of the 26 letters currently have matching counts to compare in O(1).
↗Approach
Keep need[] = counts of s1 minus counts of the current window. Count how many letters are at zero. Each slide changes two letters; update the zero count. If all 26 are zero, return true.
</>Solution (Java)
class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(), m = s2.length();
if (n > m) return false;
int[] diff = new int[26];
for (int i = 0; i < n; i++) {
diff[s1.charAt(i) - 'a']++;
diff[s2.charAt(i) - 'a']--;
}
int zeros = 0;
for (int d : diff) if (d == 0) zeros++;
for (int i = n; i < m; i++) {
if (zeros == 26) return true;
zeros += change(diff, s2.charAt(i) - 'a', -1); // char enters
zeros += change(diff, s2.charAt(i - n) - 'a', +1); // char leaves
}
return zeros == 26;
}
// applies delta to diff[c] and returns the change in the number of zero entries
private int change(int[] diff, int c, int delta) {
int before = diff[c] == 0 ? 1 : 0;
diff[c] += delta;
int after = diff[c] == 0 ? 1 : 0;
return after - before;
}
}!Common mistake
Generating all permutations of s1 — factorial time.
Complexity
- Time: O(|s1| + |s2|).
- Space: O(26).
Topic: Sliding Window
🎬 Episode 10: video coming soon