This was what I had at about 15 minutes in:
// Okay let me think of the human thing to do
// As a human, I would look for the longest cluster of strings
// I would also look for the longest clusters of strings that are separated only by k, especially if K is small.
// But I mean, mostly I'm looking for the longest clusters of strings. That's what I'm working with mostly.
// I would also be looking to see if K was at least -1 of the overall character count, because if it is, then regardless
// of characters, I really don't need to do much
function characterReplacement(s: string, k: number): number {
// Handle the case where we have so many of K that we really don't need to check what to change - we can change it all
if (k >= s.length-1) return s.length
// Create a map that stores the index of places were repeat characters start.
// The key is the index, and the value is where we record how many times they recur
// Like AAAB would be a map of 0->3, 3->1
let islands: Map<number, number> = new Map()
// Here we save the index of the last recurrence
// It starts as null
let currentIsland = null
// Iterate through the whole string
for (let i = 0; i < s.length; i++){
// If the value of the current index we're on matches the currentIsland's value, go ahead and increment that current island
if (s[currentIsland] === s[i]){
islands.set(i, islands.get(i)+1)
// Otherwise, we need to change the currentIsland. There's been a character change
// and we need to create a new entry for it.
} else {
currentIsland = i
let currentIslandValue = s[i]
}
}
console.log(islands)
};And this is what I had at 28 minutes in:
function characterReplacement(s: string, k: number): number {
if (k >= s.length-1) return s.length
let islands: Map<number, number> = new Map()
let currentIsland: number | string = "noodles"
for (let i = 0; i < s.length; i++){
if (currentIsland === "noodles"){
currentIsland = 0
islands.set(0, 1)
} else if (s[currentIsland] === s[i]){
let count = islands.get(i)
console.log(count)
islands.set(i, islands.get(i)+1)
} else {
currentIsland = i
islands.set(i, 1)
}
}
return 4
};This second example is written poorly, but I am really getting brainfreezing and it was the best I could do to just fight through and write something that made sense to me.
This creates the Map I wanted, but I don’t totally know what to do with it.
It feels like I should do some combo of finding the longest strings, and of finding the shortest spaces between them.
I suppose what I need to figure out is this
- which gaps are of a length equal to or less than
k? - If I filled those gaps, which would result in the longest contiguous strings?
This sort of falls apart in my head when I consider how multiple gaps of different characters might be filled, in all sorts of different ways. Time to look this up - it’s beyond me for now.
Here’s a pretty performant and simple example to look at:
const characterReplacement = (s: string, k: number): number => {
const hashMap: { [key: string]: number } = {}
let longest: number = 0
let maxFreq: number = 0
let leftPointer: number = 0
for (let rightPointer = 0; rightPointer < s.length; rightPointer++) {
// Increment the frequency count by 1 upon encountering a character
hashMap[s[rightPointer]] = (hashMap[s[rightPointer]] || 0) + 1
// Maximum frequency of any character encountered so far in the current window.
maxFreq = Math.max(maxFreq, hashMap[s[rightPointer]])
// Move the window from the left until reaching `k` replacements
if (maxFreq + k < rightPointer - leftPointer + 1) {
hashMap[s[leftPointer]]--
leftPointer++
}
// Calculate the longest repeating character
longest = Math.max(longest, rightPointer - leftPointer + 1)
}
return longest
}Okay I’ve been defeated for now. I’m spent. Bed time. I will hopefully return to this.
Okay got a full night’s rest and this is looking much better!
function characterReplacement(s: string, k: number): number {
const hashMap: {[key: string]: number } = {}
let longest: number = 0
let maxFreq: number = 0
let leftPointer: number = 0
for (let rightPointer = 0; rightPointer < s.length; rightPointer++){
rightChar= hashMap[s[rightPointer]]
// increment frequency count of this character by 1, or set to initial value of 1
rightChar = (rightChar || 0 ) +1
// having incremented character frequency,
// check if the last character found now has more than max frequency
// if so, update maxFreq
// This could be the same character or a different one
maxFreq = Math.max(maxFreq, rightChar)
// Is the occurence of most frequent characters in this window
// + K
// less than the number of positions in the window?
// If so, shrink the window from the left.
// This is the tricky part for me though
if (maxFreq + k < rightPointer - leftPointer + 1){
hashMap[s[leftPointer]]--
leftPointer++
}
}
};Working through the solution of someone named Jamestargia on leetcode. The solution makes a lot of sense until this part:
if (maxFreq + k < rightPointer - leftPointer + 1){
hashMap[s[leftPointer]]--
leftPointer++
}What this part of the algorithm seems to be saying is this - as soon as the most frequent character we’ve found so far as we’ve expanded right, when added with k, is less than the total positions we have in our current window, let’s shrink the window. Because we’re going from left to right, like a flashlight swept deliberately over a field looking for something. So we’ll shrink it from the left; we’ve already looked over there.
We can keep doing this until the number of positions at least reaches maxFreq + k. Because as long as we’re in that situation, we can use k to fill in the window so they are all of one character.
Looking at this, I had two concerns:
- What if decrementing
hashMap[s[leftPointer]]leads to a differentmaxFreq? - What if, as the window expands to the right, and another character becomes more frequent, we want to retroactively go back left to check that we couldn’t find a longer contiguous string with replacements using that character?
Concern #1
This is fine. maxFreq doesn’t
Concern #2
What I’m worried about is just that, if we shrink the window, what if later on we end up find a maxFreq of a different character and actually we should go back and check to see if that character can be joined with our current, later window, now that we’ve found more.
This isn’t logical though, because the left can only ‘shrink’ at the same rate that we’re adding more characters.
Let me think of it this way - K isn’t going to change. That’s set. But maxFreq can as we move along. maxFreq can potentially increase by one anytime the rightPointer increments. As long as it does, we can afford to keep the left pointer. But if we move right one and maxPointer DOESN’T increase, we can’t afford to keep our current left pointer.
But what if that leftPointer contains a character contributing to the maxFreq???
Well, if that’s the case, we’ve already calculated the farthest we can ‘afford’ to reach right from that character, and exhausted the extent of that reach. It’s farther than we can ‘reach’ using the combined power of our kand the recurring characters we’ve found. That may be the winning window! If so, those results will remain unrivaled for the remainder of our loop.
Ah. I get it in theory. But the order of some of these operations…I think I may still not entirely no know what I don’t know.
Anyway, after re-writing it, this is what I have:
function characterReplacement(s: string, k: number): number {
const hashMap: {[key: string]: number } = {}
let longest: number = 0 // <answer
let maxFreq: number = 0 // temp value to store most frequent char
let left: number = 0 // temp value to store our leftmost extent
for (let right = 0; right < s.length; right++){
hashMap[s[right]] = (hashMap[s[right]] || 0 ) +1 // increment our right value's count
maxFreq = Math.max(maxFreq, hashMap[s[right]])
// bump left to the right one
if (maxFreq + k < right - left + 1){
hashMap[s[left]]--
left++
}
// check if we have a longer window now, every time
longest = Math.max(longest, right - left + 1)
}
return longest
};Let’s see if I can write it from memory now.
Nope! That was messy. It’s just a lot of steps. Okay I’m going to rewrite this as a story. I really does feel like a drama, with characters and a plot.
Okay so it’s obviously a revolution. We have three revolutionaries, and they are surrounded by a dystopian tyranny. Think 1984 but leetcode. The problem is that everyone is expected to leetcode at least one problem everyday - not only that, but there’s a doublethink happening where leetcoding is considered the path to intelligence, beauty, rationality, and love. Goodness in all things. Our heroes are actually expert leetcoders, which is exactly why they know there is more to life than the grind. They want to rise above. They heard that once, there existed a thing called ‘art’. An irrational discipline, incomprehensible to their reality’s ruling class.
They want to overrule the status queue. But they can’t do it alone. They need to find more compatriots - but they know that if they play their hands wrong, they’ll get narced on. So they need to establish some way to find the highest concentration of sympathizers in any given leetcoding line (people line up to do leetcode on public consoles in the street, like out of pride or something).
They know that groupthink is a powerful force, one that can aide them, or work against them. If they get a critical mass within any contiguous window of people in a given line, just waiting to do their daily leetcoding, they know that they can change the minds of k people as long as the rest are already secretly sympathizers. K is a dynamic value because depending on how close the console is to the tyrants, they can get away with more or fewer converts per window.
Going one by one, they feel that they know how to determine if each individual is a sympathizer or not. Actually - it’s not so much about being a sympathizer. Everyone is a sympathizer in one way or another - the challenge is figuring out how, and making that appeal to the max number of people. Such is public speaking. So if they can find the one message to become demagogues, they can efficiently appeal to just that initial window of people, and turn them all! Revolution!
Meet our characters:
Hash: Hash is a quant. He has an excellent memory for faces and names. Everything, really. He will be counting where the sympathies of each person lie. Or rather, how many people have each type of sympathy. For example - appeal to freedom. or to love. To art. To curiosity, etc. (That’s what the numbers represent.) Hash’s job is simple, but crucial - this plan couldn’t be executed without him.
Cynthia Long: Cynthia is cantonese and knows all too from previous generations in her family what it is like to hail from a minority in world ruled by a more powerful majority. She is the leader of the group, and will be the one to make the final call - which group of people to take aside and make their crucial play. As such, she is in charge of recording the length of that group, and returning it, even though she may not pay attention to where it starts and ends.
Max Freq: Max will stick with Hash, looking over his shoulder and assisting him. They have similar jobs, but Max’s is to constantly re-assess which message will have the greatest impact based on where people’s sympathies lie. He’ll relay this to Cynthia so she knows who to address her message to.
Lefty: Every group has one - our man on the ground, our jack of all trades. Lefty is, in fact, Cynthia’s left hand man, quick to alert her to when they have overextended and need to do damage control. Maybe this is a violent operation, maybe not. They didn’t tell me.
Mr. Right: Right is the inside man.
Stay tuned! I’ll finish this story when I revisit this problem. If it’s later than November of 2024 and I still haven’t, let me know!