Permutation in String
MediumHash TableTwo PointersStringSliding Window
Solution
export function checkInclusion(s1: string, s2: string): boolean {
const [m, n] = [s1.length, s2.length];
if (m > n) {
return false;
}
const counts = new Array<number>(26).fill(0);
for (let i = 0; i < m; i++) {
counts[getIndex(s1[i])] += 1;
counts[getIndex(s2[i])] -= 1;
}
if (isMatched(counts)) {
return true;
}
for (let i = m; i < n; i++) {
counts[getIndex(s2[i])] -= 1;
counts[getIndex(s2[i - m])] += 1;
if (isMatched(counts)) {
return true;
}
}
return false;
}
function getIndex(char: string) {
return char.charCodeAt(0) - 'a'.charCodeAt(0);
}
function isMatched(counts: number[]) {
return counts.every((count) => count === 0);
}
Complexity
- Time:
O(N)
- Space:
O(1)