Jun 21, 2025

K-Special Strings: How Many Cuts Does It Take?

So I encountered this problem yesterday and I thought it would be a nice start to my blog. Sadly I’m still redesigning and setting up my CI/CD pipeline so those blogs will come a bit later

Problem Statement

You are given a string word and an integer k.

We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string.

Here, freq(x) denotes the frequency of the character x in word, and |y| denotes the absolute value of y.

Return the minimum number of characters you need to delete to make word k-special.

Approach

The most obvious first thing to do was to get the total count of each character. I have a… ritual at this point on how to do it, so I’ll just run you through it

const zerChar = "a".charCodeAt()
const getCharIdx = (char) => char.charCodeAt() - zerChar

You create a function to convert a-z to 0-25 because sadly 'b' - 'a' does not equal 1 no matter how much the big C’s try to convince you it does

const charCount = Array(26).fill(0)

You initialize the array that stores the character count

for(let i = 0; i < word.length; i++){
  charCount[getCharIdx(word[i])]++
}

And then you populate it

With that out of the way, we can start solving the problem. My initial thought was to create a sliding window of sorts, it optimally calculates where the min and max should be while making sure to delete as few excess as possible along the way

18,

23,

24,

28,

35,

38,

42,

44,

47,

50,

51,

52,

54,

59,

64,

66,

74,

79,

82,

85,

90,

Deleted Characters: 0

The logic here being, if it takes less characters to increase the minimum than it does to reduce the maximum then we should increase the minimum and vice versa

That sounds logical on the surface but then I thought of an edge case, what if it takes less to increase the minimum so I do just that, but with the new minimum, the ceiling for what the maximum can be is increased, take the example below

104,

105,

108,

110

Deleted Characters: 0

In this case, by moving from 4 to 104 suddenly the range reduces from 108 - 4 to 104 - 4. There’s suddenly a lot more leeway on what the maximum can be, heck we could go back to 110 and save some characters, but the algorithm is designed to move only forward and that makes us miss really good ranges like 104 - 110

A few minutes on the whiteboard and I sighed, we’re dealing with an array of 26, is there really a need to be optimal?

So I went at it, bull in hand like the brute I could be, and came up with this solution

const zerChar = "a".charCodeAt()
const getCharIdx = (char) => char.charCodeAt() - zerChar
var minimumDeletions = function(word, k) {
  const charCount = Array(26).fill(0)

  for(let i = 0; i < word.length; i++){
    charCount[getCharIdx(word[i])]++
  }

  charCount.sort((a, b) => a - b)
  let min = 0, i = 0, baseDeleted = 0, ans = Number.MAX_SAFE_INTEGER
  while(i < 26 && baseDeleted < ans){
    let extraDeleted = 0
    for(let j = i; j < 26; j++){
      extraDeleted += Math.max(0, charCount[j] - charCount[i] - k)
    }
    ans = Math.min(ans, extraDeleted + baseDeleted)

    baseDeleted += charCount[i]
    i++
    while(i < 26 && charCount[i] === charCount[i - 1]){
      baseDeleted += charCount[i]
      i++
    }
  }

  return ans
}

You might have noticed it has some of the echoes of our previous attempt at an optimal solution (baseDeleted, extraDeleted) but I’ll run you through what it ended up becoming

charCount.sort((a, b) => a - b)

The first thing I did was to sort the charCount array, that way I can iterate through the array from the minimum to the next minimum

baseDeleted += charCount[i]

Once I had that setup, I “cached” - heavy on the emphasis - the count of the previous minimums, the logic being, if I have a minimum character count of 5 then there shouldn’t be any character count less than 5, if there was, that would be the minimum.

let extraDeleted = 0
for(let j = i; j < 26; j++){
  extraDeleted += Math.max(0, charCount[j] - charCount[i] - k)
}

Finally, I ran a loop through the remaining surviving characters and chipped a bit off from them so anyCharacterCount - minimum would always be <= k

…I lied

I really tried being a brute but I couldn’t see it all the way through

while(i < 26 && charCount[i] === charCount[i - 1]){
  baseDeleted += charCount[i]
  i++
}

I skipped characters with a similar count because if there were two characters with the same (minimum) character count then extraDeleted would have the same result, the only difference would be at baseDeleted. And we already know baseDeleted only grows the further down the array we go

baseDeleted += charCount[i]

So there’s no point running the calculations again on the next character with the same count, as it’s guaranteed to be more than the first

All that led to this beauty 100% Leetcode submission

… hey! My website’s a mess right now but if you want to stick around here’s a disocrd channel: https://discord.gg/znPPtUvQ

In the coming weeks, I’ll work on renewing the discord link automatically, creating a webhook, a system for secrets management, and consuming rss feeds with notion. The blog will be my sanity check along the way and I can’t wait to share ideas with you!