mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-05 00:01:37 +08:00
86d333ee94
* chore: Switch to Node 20 + Vitest * chore: migrate to vitest mock functions * chore: code style (switch to prettier) * test: re-enable long-running test Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime! see #1193 * chore: code style * chore: fix failing tests * Updated Documentation in README.md * Update contribution guidelines to state usage of Prettier * fix: set prettier printWidth back to 80 * chore: apply updated code style automatically * fix: set prettier line endings to lf again * chore: apply updated code style automatically --------- Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
59 lines
1.7 KiB
JavaScript
59 lines
1.7 KiB
JavaScript
/**
|
|
* @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
|
|
* These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
|
|
* Sliding window technique reduces the required time to linear O(n).
|
|
* @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
|
|
*/
|
|
/**
|
|
* @function PermutationinString
|
|
* @description Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
|
|
* @param {String} s1 - The input string
|
|
* @param {String} s2 - The input string
|
|
* @return {boolean} - Returns true if s2 contains a permutation of s1, or false otherwise.
|
|
*/
|
|
|
|
export function PermutationinString(s1, s2) {
|
|
if (s1.length > s2.length) return false
|
|
let start = 0
|
|
let end = s1.length - 1
|
|
const s1Set = SetHash()
|
|
const s2Set = SetHash()
|
|
for (let i = 0; i < s1.length; i++) {
|
|
s1Set[s1[i]]++
|
|
s2Set[s2[i]]++
|
|
}
|
|
if (equals(s1Set, s2Set)) return true
|
|
while (end < s2.length - 1) {
|
|
if (equals(s1Set, s2Set)) return true
|
|
end++
|
|
const c1 = s2[start]
|
|
const c2 = s2[end]
|
|
if (s2Set[c1] > 0) s2Set[c1]--
|
|
s2Set[c2]++
|
|
start++
|
|
if (equals(s1Set, s2Set)) return true
|
|
}
|
|
return false
|
|
}
|
|
function equals(a, b) {
|
|
return JSON.stringify(a) === JSON.stringify(b)
|
|
}
|
|
|
|
function SetHash() {
|
|
const set = new Set()
|
|
const alphabets = 'abcdefghijklmnopqrstuvwxyz'
|
|
for (let i = 0; i < alphabets.length; i++) {
|
|
set[alphabets[i]] = 0
|
|
}
|
|
return set
|
|
}
|
|
|
|
// Example 1:
|
|
// Input: s1 = "ab", s2 = "eidbaooo"
|
|
// Output: true
|
|
// Explanation: s2 contains one permutation of s1 ("ba").
|
|
|
|
// Example 2:
|
|
// Input: s1 = "ab", s2 = "eidboaoo"
|
|
// Output: false
|