2516. Take K of Each Character From Left and Right

MediumView on LeetCode

Hash Table String Sliding Window

Time: O(n)

Space: O(1)

Intuition

Minimum deletions to make string of k distinct characters. Count frequencies, sort, delete smallest frequencies first.

Algorithm

1Count frequencies. If distinct <= k: return 0. Sort frequencies ascending. Delete smallest until k remain.

Common Pitfalls

•We want exactly k distinct characters. Delete characters with smallest frequencies entirely first.

2516.cs

// Approach: Sliding window on excluded middle; maximize exclusion while keeping ≥k of each char.
// Time: O(n) Space: O(1)

public class Solution
{
    public int TakeCharacters(string s, int k)
    {
        int n = s.Length;
        int ans = n;
        int[] count = new int[3];

        foreach (char c in s)
            count[c - 'a']++;

        if (count[0] < k || count[1] < k || count[2] < k)
            return -1;

        for (int l = 0, r = 0; r < n; r++)
        {
            count[s[r] - 'a']--;
            while (count[s[r] - 'a'] < k)
            {
                count[s[l] - 'a']++;
                l++;
            }
            ans = Math.Min(ans, n - (r - l + 1));
        }

        return ans;
    }
}

Was this solution helpful?