Network Network Synthesizer 9 — Problem Statement & Solution Guide

StringsEasyFixed/Dynamic Window

TimeO(n)

SpaceO(1)

Problem Description

You are given a string s consisting of lowercase English letters and an integer k. Your task is to determine the minimum number of character deletions required to ensure that no character appears more than k times in the resulting string. If the string already satisfies this condition, return 0. The goal is to compute the optimal reduction count to meet the frequency constraint.

DSA Pattern Breakdown

"Network Network Synthesizer 9"

easy

WHY DOES IT MATTER?

Frequency capping is a classic counting problem that appears in data sanitization, rate limiting, and compression scenarios; mastering it demonstrates the ability to translate constraints into simple arithmetic over aggregates.

OPTIMIZATION CHALLENGE

The key insight is that deletions for each character are independent, so the global optimum is the sum of per‑character excesses, eliminating the need for combinatorial search.

REAL-WORLD CONNECTION

Think of a distributed logging system that must not store more than k entries per user per day; excess logs are dropped, analogous to deleting characters that exceed the allowed frequency.

During an interview, compute the frequency array first, then loop over it once to accumulate max(0, freq - k). This two‑step pattern (count then aggregate) is a go‑to for many "limit per item" problems.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to counting the frequency of each character in the input string and ensuring that no count exceeds the threshold k. A naive solution would iterate over every possible subset of characters to delete, which is exponential and infeasible for strings of length up to 10^5. The optimal paradigm leverages a frequency map (often an array of size 26 for lowercase letters) to compute the excess occurrences for each character, and the answer is simply the sum of those excesses, because deletions are independent across characters and any excess character can be removed without affecting the feasibility of others.

Interview Questions on This Problem

Q1How would you modify the solution if the string could contain any Unicode character, not just lowercase English letters?

Replace the fixed-size 26-element array with a hash map (e.g., unordered_map<char, int> in C++ or dict in Python) to store frequencies, then iterate over the map to sum max(0, freq - k). The time remains O(n) and space becomes O(u) where u is the number of distinct characters.

Q2Can you extend the algorithm to also return the lexicographically smallest resulting string after deletions?

First compute the excess count for each character. Then traverse the original string, appending a character only if its remaining allowed quota (>0) is positive, decrementing the quota each time. This greedy pass preserves original order and yields the smallest lexicographic result because we never reorder characters.

Q3What would be the impact on time and space complexity if the input string length is 10^7 and you must process it in a streaming fashion?

A streaming approach still uses O(1) additional space (26 counters) because you can update frequencies on the fly; however, you need a second pass or a buffer to decide deletions, which may require O(1) extra memory if you output deletions directly. Overall time stays O(n) with a single pass.

Examples

Example 1

Input

s = "aaabbc", k = 2

Output

Explanation: The frequency of 'a' is 3, which exceeds k=2. We must delete 1 'a'. The frequencies of 'b' (2) and 'c' (1) are within the limit. Total deletions = 1.

Example 2

Input

s = "abcdef", k = 1

Output

Explanation: Each character appears exactly once. Since 1 <= k=1, no deletions are needed. Total deletions = 0.

Example 3

Input

s = "aaaaaa", k = 3

Output

Explanation: The frequency of 'a' is 6. To reduce it to at most 3, we must delete 6 - 3 = 3 characters. Total deletions = 3.

Example 4

Input

s = "aabbaa", k = 2

Output

Explanation: Frequency of 'a' is 4 (exceeds 2, delete 2). Frequency of 'b' is 2 (within limit). Total deletions = 2.

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters only
1 <= k <= 10^5

Optimal Approach & Strategy

Build a 26‑element frequency array, compute excess = max(0, freq - k) for each letter, and sum these excesses. The sum is the minimal deletions needed.

Brute Force Approach

Try every possible subset of characters to delete and check if the remaining string satisfies the k‑frequency rule; keep the smallest subset size. This exponential search is impractical for any non‑trivial string length.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var minDeletions = function(s, k) {
    const freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    let deletions = 0;
    for (let char in freq) {
        if (freq[char] > k) {
            deletions += freq[char] - k;
        }
    }
    return deletions;
};

// Example usage
// const s = "aaabbc";
// const k = 2;
// console.log(minDeletions(s, k));

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int minDeletions(string s, int k) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        int deletions = 0;
        for (auto& p : freq) {
            if (p.second > k) {
                deletions += p.second - k;
            }
        }
        return deletions;
    }
};

int main() {
    Solution sol;
    string s;
    int k;
    cin >> s >> k;
    cout << sol.minDeletions(s, k) << endl;
    return 0;
}

import java.util.*;

class Solution {
    public int minDeletions(String s, int k) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        int deletions = 0;
        for (int count : freq.values()) {
            if (count > k) {
                deletions += count - k;
            }
        }
        return deletions;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int k = scanner.nextInt();
        System.out.println(sol.minDeletions(s, k));
    }
}

class Solution:
    def minDeletions(self, s: str, k: int) -> int:
        freq = {}
        for char in s:
            freq[char] = freq.get(char, 0) + 1
        deletions = 0
        for count in freq.values():
            if count > k:
                deletions += count - k
        return deletions

# Example usage
# sol = Solution()
# s = "aaabbc"
# k = 2
# print(sol.minDeletions(s, k))

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var minDeletions = function(s, k) {
    const freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    let deletions = 0;
    for (let char in freq) {
        if (freq[char] > k) {
            deletions += freq[char] - k;
        }
    }
    return deletions;
};

// Example usage
// const s = "aaabbc";
// const k = 2;
// console.log(minDeletions(s, k));

Asked in Top Tech Interviews

GoogleAmazonMicrosoft

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Network Network Synthesizer 9 Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Network Network Synthesizer 9 — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor