Take K of Each Character From Left and Right

Leetcode Problem:

• Take K of Each Character From Left and Right

Summary

• Given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k, find the minimum number of minutes needed to take at least k of each character.

Approach

• The approach used is to use a sliding window technique
• The window is initially set to the entire string
• If the count of each character in the window is greater than or equal to k, the window is moved to the right
• If the count of each character in the window is less than k, the window is moved to the left
• The minimum number of minutes is updated whenever a valid window is found.

Complexity

• O(N^2) where N is the length of the string

Explanation

• The solution first initializes a count array to keep track of the count of each character in the string
• It then iterates over the string and checks if the count of each character is greater than or equal to k
• If it is, the window is moved to the right
• If it is not, the window is moved to the left
• The minimum number of minutes is updated whenever a valid window is found
• The solution then returns the minimum number of minutes.

Solution Code:

class Solution {
public:
    int cnt[256];
    int takeCharacters(string s, int k) {
        int N = s.size();
        int ans= -1;
        int i;
        for(i = 0 ; i < N; i++){
            cnt[s[i]]++;
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = i+1;
                break;
            }
        }
        if(ans == -1) return -1;
        int r = N -1;
        while(i>=0){
            cnt[s[i]]--;
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = min(ans,i + N - r - 1);
                i--;
                continue;
            }
            while (r >= 0 && (cnt['a'] < k || cnt['b'] < k || cnt['c'] < k)){
                cnt[s[r]]++;
                r--;
            }
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = min(ans, i + 1 + N - r -1);
            }

            i--;
        }
        
        return ans;
    }
};