We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Deletions to Make String K-Special

Number: 3360

Difficulty: Medium

Paid? No

Companies: DE Shaw

Problem Description

Given a string word and an integer k, we say that word is k‑special if for any two characters present in word, the difference in their frequency (after optionally deleting some characters) is at most k. In other words, if you let freq(x) denote the frequency of character x in the final string, then for every pair of characters present in that string the condition |freq(x) - freq(y)| ≤ k holds. The task is to find the minimum number of deletions required to make the string k‑special.

Key Insights

  • There are only 26 lowercase letters, so we only have up to 26 frequency counts.
  • For each letter, you can choose to keep some occurrences (from 0 up to its original count); if a letter is dropped completely, it does not contribute to the k-special condition.
  • To guarantee the k‑special property for the remaining letters, their kept frequencies must all lie within a contiguous interval [L, R] such that R − L ≤ k.
  • For a fixed interval [L, L+k], if a letter’s frequency f is below L then it cannot “raise” its frequency (we are only allowed to delete) so that letter must be dropped; if f is between L and L+k, keep f; and if f is greater than L+k, keep only L+k.
  • Iterate over possible values of L (from 1 to the maximum frequency among letters) and compute the maximum total kept occurrences. The minimum deletions equal (total characters – maximum kept).

Space and Time Complexity

Time Complexity: O(max_f * 26) where max_f is the maximum frequency among the 26 letters (max_f ≤ 10^5), which is acceptable. Space Complexity: O(26) = O(1) for storing frequency counts.

Solution

We begin by computing the frequency of each character in the given word. For any candidate lower bound L of our allowed kept frequency interval [L, L+k], we determine for each letter:

  • If its frequency is less than L, we cannot include it (must delete all occurrences).
  • Otherwise, we can keep min(f, L+k) occurrences. Summing these kept counts across all letters gives the total number of characters that remain if we force the kept frequencies to lie in [L, L+k]. We try all possible L (from 1 to maximum frequency) and choose the one that leads to the maximum retained count. The answer is then the original length of the string minus this maximum.

Key points:

  • Only letters with frequency at least L can be partially kept.
  • For letters with frequency greater than L+k, we are forced to delete the extra occurrences.
  • By iterating L over the valid range (1..max_f), we effectively search through all potential choices for the minimum kept frequency among the chosen letters.

Code Solutions

# Python solution with detailed comments

def minDeletions(word, k):
    # Calculate frequency of each character (only 26 lowercase letters)
    freq = {}
    for char in word:
        freq[char] = freq.get(char, 0) + 1

    # Gather all frequencies in a list
    frequencies = list(freq.values())
    
    # Total number of characters in original word
    total_chars = len(word)
    
    # List might be empty but word length is at least 1 by constraint
    max_freq = max(frequencies)
    
    # Variable to track the maximum number of kept characters
    best_kept = 0

    # Try each possible lower bound L of the kept frequency range [L, L+k]
    for L in range(1, max_freq + 1):
        current_kept = 0
        # For each letter frequency f in frequencies
        for f in frequencies:
            if f < L:
                # Cannot meet the lower bound, so this letter is not kept
                continue
            else:
                # If f is at least L, optimal kept count for this letter is min(f, L+k)
                current_kept += min(f, L + k)
        # Update best_kept if we found a better configuration
        best_kept = max(best_kept, current_kept)
    
    # The minimum deletions is the characters removed from total
    return total_chars - best_kept

# Example usage:
print(minDeletions("aabcaba", 0))  # Expected output: 3
print(minDeletions("dabdcbdcdcd", 2))  # Expected output: 2
print(minDeletions("aaabaaa", 2))  # Expected output: 1
← Back to All Questions