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

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int start = 0;
        long res = 0;
        long sum = 0;
        Set<Integer> set = new HashSet<>();
        for(int end = 0; end < n; end++) {
            while(set.contains(nums[end])) {
                sum -= nums[start];
                set.remove(nums[start++]);
            }
            sum += nums[end];
            set.add(nums[end]);
            if(end - start + 1 == k) {
                res = Math.max(res, sum);
                sum -= nums[start];
                set.remove(nums[start++]);
            }
        
        }
        
        return res;
    }
}

func maximumSubarraySum(nums []int, k int) int64 {
    if len(nums) < k {
        return 0
    }

    tmpNum := int64(0)
    maxSum := int64(0)
    m := make(map[int]int)

    for i := 0; i < k; i++ {
        tmpNum += int64(nums[i])
        m[nums[i]]++
    }
    if len(m) == k {
        maxSum = tmpNum
    }

    for i := k; i < len(nums); i++ {
        prev := nums[i-k]
        m[prev]--
        if m[prev] == 0 {
            delete(m, prev)
        }
        tmpNum -= int64(prev)

        next := nums[i]
        m[next]++
        tmpNum += int64(next)

        if len(m) == k {
            if tmpNum > maxSum {
                maxSum = tmpNum
            }
        }
    }

    return maxSum
}

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap();
        int freqSum = 0;
        long sum = 0;
        long max = 0;
        for(int i = 0;i<nums.length;i++){
            int f = 0;
            if (map.containsKey(nums[i]))
                f = map.get(nums[i]);
            map.put(nums[i],f+1);
            freqSum+=f+1;
            sum+=nums[i];
            if(i>=k-1){
                if(freqSum==k)
                    max = Math.max(max,sum);
                int freq = map.get(nums[i-k+1]);
                freqSum-=freq;
                sum -= nums[i-k+1];
                map.put(nums[i-k+1],freq-1);
            }
        }
        return max;
    }
}

public class Solution {
    public long MaximumSubarraySum(int[] nums, int k) {
        Dictionary<int, int> dict = new Dictionary<int, int>();
        long sum = 0;
        int l = 0;
        int r = 0;
        long result = 0;
        while (r < nums.Length)
        {
            sum += nums[r];
            if(dict.ContainsKey(nums[r]))
            {
                r = dict[nums[r]]+1;
                l = r;
                sum = 0;
                dict.Clear();
                continue;
            }
            else
            {
                dict.Add(nums[r], r);
            }
            if(r-l+1 == k)
            {
                if(sum > result)
                    result = sum;
                    
                sum -= nums[l];
                dict.Remove(nums[l]);
                l++;
                r++;
            }
            else
                r++;
        }
        return result;
    }
}

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        n = len(s)
        a, b, c = 0, 0, 0
        countLeft = [[0]*3 for _ in range(len(s) + 1)]
        countRight = [[0]*3 for _ in range(len(s) + 1)]
        for i in range(len(s)):
            if s[i] == 'a':
                a += 1
            if s[i] == 'b':
                b += 1
            if s[i] == 'c':
                c += 1
            countLeft[i + 1] = [a, b, c]

        a, b, c = 0, 0, 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == 'a':
                a += 1
            if s[i] == 'b':
                b += 1
            if s[i] == 'c':
                c += 1
         
            countRight[n - i] = [a, b, c]

        def bisearch(minute):
            for i in range(0, minute + 1):
                if countLeft[i][0] + countRight[minute - i][0] >= k and countLeft[i][1] + countRight[minute - i][1] >= k and countLeft[i][2] + countRight[minute - i][2] >= k:
                    return True
             
            return False

        ans = -1
        left = 0
        right = n
        while left <= right:
            mid = left + (right - left)//2
            if bisearch(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        return ans

class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        count = [0]*3
        for char in s:
            count[ord(char) - ord('a')] += 1
        for i in range(3):
            count[i] -= k
            if count[i] < 0:
                return -1
                
        current = [0]*3
        left = 0
        n = len(s)
        ans = inf
        for right in range(n):
            current[ord(s[right]) - ord('a')] += 1
            while current[0] > count[0] or current[1] > count[1] or current[2] > count[2]:
                current[ord(s[left]) - ord('a')] -= 1
                left += 1
            ans = min(n - (right - left + 1), ans)
        return ans

class Solution {
public:
    int takeCharacters(string s, int k) {
        vector<int> freq(3, 0), window_freq(3, 0);

        for (const char &c : s) {
            freq[c-'a'] += 1;
        }

        for (char c = 'a'; c <= 'c'; ++c) {
            if (freq[c-'a'] < k) {
                return -1;
            }
        }

        int res = INT_MAX;

        for (int l=0, r=0; r<s.size(); ++r) {
            ++window_freq[s[r]-'a'];

            while (l<=r && freq[s[r]-'a'] - window_freq[s[r]-'a'] < k) {
                --window_freq[s[l++]-'a'];
            }

            res = min(res, (int)s.size() - r + l -1);


        }

        return res;
    }
};

class Solution {
    public int takeCharacters(String s, int k) {
        if (k == 0)
            return 0;

        int[] map = new int[3];
        for (char c : s.toCharArray()) {
            map[c - 'a']++;
        }

        if (map[0] < k || map[1] < k || map[2] < k) {
            return -1;
        }

        int n = s.length();
        int[] window = new int[3];
        int left = 0, max = 0;

        for (int right = 0; right < n; right++) {
            window[s.charAt(right) - 'a']++;

            while (window[0] > map[0] - k ||
                   window[1] > map[1] - k ||
                   window[2] > map[2] - k) {
                window[s.charAt(left) - 'a']--;
                left++;
            }

            max = Math.max(max, right - left + 1);
        }

        return n - max;
    }
}

class Solution {
public:
    int takeCharacters(string s, int k) {
            int n = s.length();
        vector<int> aIndex;
        vector<int> bIndex;
        vector<int> cIndex;

        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == 'c') cIndex.push_back(n - i);
            if (s[i] == 'b') bIndex.push_back(n - i);
            if (s[i] == 'a') aIndex.push_back(n - i);
        }

        if (aIndex.size() < k || bIndex.size() < k || cIndex.size() < k) {
            return -1;
        }

        if (k == 0) return 0;

        int currentA = 0;
        int currentB = 0;
        int currentC = 0;

        int ans = max(aIndex[k - 1], max(bIndex[k - 1], cIndex[k - 1]));


        for (int i = 0; i < n; i++) {
            if (currentA <= k  && s[i] == 'a') currentA++;
            else if (currentB <= k && s[i] == 'b') currentB++;
            else if (currentC <= k && s[i] == 'c') currentC++;

            if (currentA >= k && currentB >= k && currentC >= k) {
                ans = min(ans, i + 1);
                break;
            }

            int temp = - 1;

            if (currentA < k) temp = max(temp, aIndex[k - currentA - 1]);
            if (currentB < k) temp = max(temp, bIndex[k - currentB - 1]);
            if (currentC < k) temp = max(temp, cIndex[k - currentC - 1]);
            temp = i + 1 + temp;

            ans = min(ans, temp);
        }

        return ans;
    }
};

function takeCharacters(s: string, k: number): number {
    let n = s.length, countA = 0, countB = 0, countC = 0, res = n;
    for (let i = 0; i < n; i++) {
        if (s[i] === 'a') countA++;
        else if (s[i] === 'b') countB++;
        else countC++;
    }
    if (countA < k || countB < k || countC < k) return -1;
    let l = n - 1, r = n - 1;
    while (l >= 0) {
        if (s[l] === 'a') countA--;
        else if (s[l] === 'b') countB--;
        else if (s[l] === 'c') countC--;
        while (countA < k || countB < k || countC < k) {
            if (s[r] === 'a') countA++;
            else if (s[r] === 'b') countB++;
            else if (s[r] === 'c') countC++;
            r--;
        }
        res = Math.min(res, n - (r - l + 1));
        l--
    }
    return res;
};

class Solution {
    public int takeCharacters(String s, int k) {
        int n = s.length();
        int[] freq = new int[3];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        if (freq[0] < k || freq[1] < k || freq[2] < k) return -1;
        int[] arr = new int[3];
        int l = 0, max = 0;
        for (int r = 0; r < n; r++) {
            arr[s.charAt(r) - 'a']++;
            while (l <= r && (freq[0] - arr[0] < k || freq[1] - arr[1] < k || freq[2] - arr[2] < k )) {
                arr[s.charAt(l) - 'a']--;
                l++;
            }
            max = Math.max(r - l + 1, max);
        }
        return n - max;
    }
}

var takeCharacters = function (s, k) {
    const n = s.length, m = { a: 0, b: 0, c: 0 };
    for (const ch of s) {
        m[ch]++;
    }
    for (const ch of 'abc') {
        m[ch] -= k;
        if (m[ch] < 0) {
            return -1;
        }
    }
    let max = 0;
    for (let i = 0, j = 0; i < n; i++) {
        const ch = s[i];
        m[ch]--;
        while (m[ch] < 0) {
            m[s[j++]]++;
        }
        max = Math.max(max, i - j + 1);
    }
    return n - max;
};