thảo luận Leetcode mỗi ngày

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        d = Counter(s1)
        n = len(s2)
        l = 0
        found = len(s1)
        for r in range(n):
            if s2[r] in d and d[s2[r]] > 0:
                d[s2[r]] -= 1
                found -= 1
                if found == 0:
                    return True
            else:
                while s2[l] != s2[r]:
                    if s2[l] in d:
                        d[s2[l]] += 1
                        found += 1
                    l += 1
                l += 1
       
        return False

public class Solution
{
    public bool CheckInclusion(string s1, string s2)
    {
        if (s1.Length > s2.Length)
        {
            return false;
        }
        
        int[] s1Map = new int[26];
        int[] s2Map = new int[26];
        
        for (int i = 0; i < s1.Length; i++)
        {
            s1Map[s1[i] - 'a']++;
            s2Map[s2[i] - 'a']++;
        }
        
        int count = 0;       
        for (int i = 0; i < s1Map.Length; i++)
        {
            if (s1Map[i] != s2Map[i])
            {
                continue;
            }
            
            count++;
        }
        
        for (int i = 0; i < s2.Length - s1.Length; i++)
        {
            if (count == 26)
            {
                return true;
            }
            
            int left = s2[i] - 'a';
            int right = s2[s1.Length + i] - 'a';
            
            s2Map[right]++;
            if (s1Map[right] == s2Map[right])
            {
                count++;
            }
            
            if (s1Map[right] + 1 == s2Map[right])
            {
                count--;
            }
            
            s2Map[left]--;
            if (s1Map[left] == s2Map[left])
            {
                count++;
            }
            
            if (s1Map[left] - 1 == s2Map[left])
            {
                count--;
            }
        }
        
        return count == 26;
    }
}

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        guard s1.count <= s2.count else { return false }
        var s1Dict:[Character: Int] = [:]
        for c in s1 {
            s1Dict[c, default:0] += 1
        }
        var s2Dict:[Character: Int] = [:]
        let s2 = [Character](s2)
        for index in 0..<s1.count {
            s2Dict[s2[index], default:0] += 1
        }
        //
        func isSameDict(_ add: Character? = nil, _ remove: Character? = nil) -> Bool {
            if s1Dict.count != s2Dict.count {
               return false
            }
            if let add = add {
                if s1Dict[add, default: 0] != s2Dict[add, default: 0] {
                    return false
                }
            }
            if let remove = remove {
                if s1Dict[remove, default: 0] != s2Dict[remove, default: 0] {
                    return false
                }
            }
            return s1Dict == s2Dict
        }
        if isSameDict() { return true }
        //
        var l = 0
        var r = s1.count-1
        while r < s2.count-1 {
            r += 1
            let lChar = s2[l]
            let rChar = s2[r]
            s2Dict[rChar, default:0] += 1
            s2Dict[lChar]! -= 1
            if s2Dict[lChar]! == 0 {
                s2Dict[lChar] = nil
            }
            l += 1
            if isSameDict(rChar, lChar) { return true }
        }

        return false
    }
}

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s1.length() > s2.length()) return false;

        int s1Freq[26] = { 0 }; for (auto& c : s1) { s1Freq[c - 'a'] += 1; }
        int w2Freq[26] = { 0 }; for (auto c = s2.begin(); c < s2.begin() + s1.length(); ++c) { w2Freq[*c - 'a'] += 1; }
        auto is_equal = [&s1Freq, &w2Freq]() {
            for (size_t i = 0; i < 26; ++i) { if (s1Freq[i] != w2Freq[i]) return false; }
            return true;
        };

        auto left = s2.begin(); auto right = left + s1.length() - 1;
        for (;;) {
            if (is_equal()) return true;
            w2Freq[*left - 'a'] -= 1;
            ++left; ++right; if (right == s2.end()) break;
            w2Freq[*right - 'a'] += 1;
        }
        return false;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> f1(26), f2(26);
        for (char c : s1) f1[c - 'a']++;
        int l = 0, r = 0;
        while (r < s2.size()) {
            if (r - l + 1 < s1.size()) f2[s2[r] - 'a']++;
            else {
                f2[s2[r] - 'a']++;
                if (f1 == f2) return true;
                f2[s2[l] - 'a']--;
                l++;
            }
            r++;
        }
        return false;
    }
};

impl Solution {
    pub fn check_inclusion(s1: String, s2: String) -> bool {
        let (mut s1_freqs, mut window_freqs)= (vec![0; 26], vec![0; 26]);
        let mut left = 0;

        for bc in s1.as_bytes().into_iter().copied() {
            s1_freqs[(bc - b'a') as usize] += 1;
        }

        let mut max_match_count =
            s1_freqs.iter().copied().filter(|&freq| freq != 0).count();

        let mut match_count = 0;

        let s2_bytes = s2.as_bytes();

        for (right, bc) in s2.as_bytes().into_iter().copied().enumerate() {
            let mut ibc = (bc - b'a') as usize;

            if s1_freqs[ibc] == 0 && match_count > 0 {
                window_freqs.iter_mut().for_each(|freq| *freq = 0);
                left = right + 1;
                match_count = 0;

                continue;
            }

            window_freqs[ibc] += 1;

            if window_freqs[ibc] == s1_freqs[ibc] {
                match_count += 1;
            }

            while left <= right && window_freqs[ibc] > s1_freqs[ibc] {
                let ilbc = (s2_bytes[left] - b'a') as usize;

                if window_freqs[ilbc] == s1_freqs[ilbc] {
                    match_count -= 1;
                }

                window_freqs[ilbc] -= 1;

                left += 1;
            }

            if match_count == max_match_count {
                return true;
            }
        }

        false
    }
}

impl Solution {
    pub fn check_inclusion(s1: String, s2: String) -> bool {
        let (mut s1_freqs, mut window_freqs)= (vec![0; 26], vec![0; 26]);
        let mut left = 0;

        for bc in s1.as_bytes().into_iter().copied() {
            s1_freqs[(bc - b'a') as usize] += 1;
        }

        let mut max_match_count =
            s1_freqs.iter().copied().filter(|&freq| freq != 0).count();

        let mut match_count = 0;

        let s2_bytes = s2.as_bytes();

        for (right, bc) in s2.as_bytes().into_iter().copied().enumerate() {
            let mut ibc = (bc - b'a') as usize;

            window_freqs[ibc] += 1;
            if window_freqs[ibc] == s1_freqs[ibc] {
                match_count += 1;
            }

            while left <= right && window_freqs[ibc] > s1_freqs[ibc] {
                let ilbc = (s2_bytes[left] - b'a') as usize;

                if window_freqs[ilbc] == s1_freqs[ilbc] {
                    match_count -= 1;
                }

                window_freqs[ilbc] -= 1;

                left += 1;
            }

            if match_count == max_match_count {
                return true;
            }
        }

        false
    }
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int l = 0, r = 0;
        while (r <= s2.length()) {
            if ((r - l) == s1.length()) {
                String s = s2.substring(l, r);
                if (permutation(s, s1)) return true;
                l++;
            }
            r++;
        }
        return false;
    }

    public boolean permutation(String s1, String s2) {
        int[] freq = new int[26];
        for (char c : s1.toCharArray()) {
            freq[c - 'a']++;
        }
        for (char c: s2.toCharArray()) {
            freq[c - 'a']--;
        }
        for (int i : freq) {
            if (i != 0) return false;
        }
        return true;
    }
}

class Solution {
    int[] target = new int[26];
    int[] slide = new int[26];
    
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();

        if (len2 < len1) return false;
        
        init(target, s1);
        init(slide, s2.substring(0, len1));
        
        for (int i = len1; i < len2; i++) {
            if (compare()) return true;
            
            slide[s2.charAt(i - len1) - 'a']--;
            slide[s2.charAt(i) - 'a']++;
        }
        
        return compare();
    }
    
    void init(int[] arr, String str) {
        for (int i = 0; i < str.length(); i++) {
            arr[str.charAt(i) - 'a']++;
        }
    }
    
    boolean compare() {
        for (int i = 0; i < 26; i++) {
            if (target[i] != slide[i])
                return false;
        }
        
        return true;
    }
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        if (ch2.length < ch1.length) return false;
        int[] freq1 = freqLc(ch1);
        for (int i = 0; i <= ch2.length - ch1.length; i++) {
            char[] sub2 = s2.substring(i, i + ch1.length).toCharArray();
            if (java.util.Arrays.equals(freq1, freqLc(sub2))) return true;
        }
        return false;
    }

    static int[] freqLc(char[] ch) {
        int[] freq = new int[26];
        for (char c : ch) freq[c - 'a']++;
        return freq;
    }
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character, Integer> s1Freq = new HashMap<>();
        HashMap<Character, Integer> s2Freq = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            char ch = s1.charAt(i);
            s1Freq.put(ch, s1Freq.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s2.length(); i++) {
            char ch = s2.charAt(i);
            s2Freq.put(ch, s2Freq.getOrDefault(ch, 0) + 1);
            if (i >= s1.length() - 1) {
                if (check(s1Freq, s2Freq)) {
                    return true;
                } else {
                    char removeChar = s2.charAt(i - s1.length() + 1);
                    s2Freq.put(removeChar, s2Freq.getOrDefault(removeChar, 0) - 1);
                }
            }
        }
        return false;
    }
    private boolean check(HashMap<Character, Integer> m1, HashMap<Character, Integer> m2) {
        for (Character ch : m1.keySet()) {
            if (m1.get(ch) - m2.getOrDefault(ch, 0) != 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool checkInclusion(string const& s1, string const& s2) {
        int n1 = s1.size(), n2 = s2.size();
        if (n1 > n2) return false;
        int counter[26] = {}, matches = 0;
        for (char c : s1) counter[c - 'a']++;
        for (int i = 0; i < n1; ++i) counter[s2[i] - 'a']--;
        for (int i = 0; i < 26; ++i) matches += counter[i] == 0;
        if (matches == 26) return true;
        for (int i = n1; i < n2; ++i) {
            int pos = s2[i] - 'a', neg = s2[i - n1] - 'a';
            counter[pos]--;
            if (counter[pos] == 0) matches++;
            else if (counter[pos] == -1) matches--;
            
            counter[neg]++;
            if (counter[neg] == 0) matches++;
            else if (counter[neg] == 1) matches--;
            if (matches == 26) return true;
        }
        return false;
    }
};