[JS] Permutation in String

🔒 문제 (LeetCode 567)

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘 - sliding window

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    let map = new Map();	// s1의 문자 개수 세기
    const len = s1.length;

    for(let i = 0; i < len; i++) {
       map.set(s1[i], map.get(s1[i]) + 1 || 1);
    }
    
    let l = 0;
    let cnt = map.size;
    for(let r = 0; r < s2.length; r++) {
        const char = s2[r];
        if(map.has(s2[r])) map.set(char, map.get(char) - 1);
        if(map.get(char) === 0) cnt--;
        
        while(cnt === 0) {
            if(r - l + 1 === len) return true;  // window 사이즈와 같으면 탐색 완료
            if(map.has(s2[l])) map.set(s2[l], map.get(s2[l]) + 1);  // window의 시작 문자 개수 제외
            if(map.get(s2[l]) === 1) cnt++; // window의 시작 문자를 제외했으므로 하나 더 추가
            l++;    // window 한 칸 옮기기
        }
    }
    return false;
};