Game with String

JavaView on GFG

Intuition

Minimize maximum frequency after removing k characters. Priority queue on frequency counts.

Algorithm

1Count frequencies. Max-heap. Remove k characters from highest-frequency chars one by one.
2Actually: greedily reduce top frequencies. Max-heap, pop top, decrement, push back. Repeat k times.

Common Pitfalls

•Greedy: always remove from most frequent. After k removals, answer = top of heap.

Game with String.java

Java

// Approach: Greedy with max-heap. Remove the most frequent character k times, minimize distinct remaining.
// Time: O(n + k log 26) Space: O(26)
import java.util.*;

class Solution {
    public int minValue(String s, int k) {
        int freq[] = new int[26];

        for (int c : s.toCharArray())
            freq[c - 'a']++;

        while (k > 0) {
            Arrays.sort(freq);
            if (freq[25] == 0)
                break;
                
            freq[25]--;
            k--;
        }

        int result = 0;

        for (int i = 25; i >= 0; i--) {
            if (freq[i] == 0)
                continue;

            result += freq[i] * freq[i];
        }

        return result;
    }
}

Was this solution helpful?