0% completed
Longest Substring with Same Letters after Replacement (hard)
Problem Statement
Given a string with lowercase letters only, if you are allowed to replace no more than ‘k’ letters with any letter, find the length of the longest substring having the same letters after replacement.
Example 1:
Input: str="aabccbb", k=2
Output: 5
Explanation: Replace the two 'c' with 'b' to have a longest repeating substring "bbbbb".
Example 2:
Input: str="abbcb", k=1
Output: 4
Explanation: Replace the 'c' with 'b' to have a longest repeating substring "bbbb".
Example 3:
Input: str="abccde", k=1
Output: 3
.....
.....
.....
Jared
· 4 years ago
Hard problems should come with a visual component, often times just writing a paragraph explanation will not suffice.
ahonliu
· 2 years ago
When the window shrinks, it is possible that maxRepeatLetterCount reduces, right?
Viacheslav Lushchinskiy
· 4 years ago
The solution is elegant but hard to understand. The tiny change to the solution could make it easier to comprehend. Maybe less efficient but probably with the same O(N)
My algorithm :
- keep track of the sum of all characters in the frequency hashmap
- on each iteration extract the value of the max repeating character in that hashmap
- if the remaining sum is more than K, shrink the window.
The hole solution in JS: const f = (_str, _k) => { let windowStart = 0; let maxLength = 0; const charFrequency = {}; let allCharSum = 0;
for (let windowEnd = 0; windowEnd < _str.length; windowEnd++) { const rightChar = _str[windowEnd];
if (!(rightChar in charFrequency)) { charFrequency[rightChar] = 0; } charFrequency[rightChar] += 1; allCharSum += 1;
// Find the max value and delete it from the ov
Mikhail Putilov
· 4 years ago
That's an incredibly poor explanation for the non-trivial solution
sw94070
· a year ago
In the shrinking window part:
// current window size is from windowStart to windowEnd, overall we have a letter
// which is repeating 'maxRepeatLetterCount' times, this means we can have a window
// which has one letter repeating 'maxRepeatLetterCount' times and the remaining
// letters we should replace. If the remaining letters are more than 'k', it is the
// time to shrink the window as we are not allowed to replace more than 'k' letters
if (windowEnd - windowStart + 1 - maxRepeatLetterCount > k) {
char leftChar = str.charAt(windowStart);
letterFrequencyMap.put(leftChar, letterFrequencyMap.get(leftChar) - 1);
windowStart++;
}
What if the chatAt(windowSt
stephen
· 4 years ago
While the algo produces the correct result it incorrectly calculates the max_length even though the window is invalid.
When start = 0, end = 4, max_repeat = 2, max_len = 4; you will enter the while loop and increment start. Now start = 1 and this still is not a valid window but you will not enter the while loop since 2 !> 2.
Since the iteration before max = 3-0, this time max = 4-1 which is the same answer since you are just shifting the window but you shouldn't be calculating the max_window when the constraint is not met.
I get the idea of using a generalized solution but this can be confusing for someone who is writing out the code and confused about why we are calculating max on an invalid window.
Lex
· 4 years ago
Why here using if condition to shrink the window but using while condition in the solution to Longest Substring with K Distinct Characters?
Austin McDaniel
· 4 years ago
from collections import Counter class Solution: def characterReplacement(self, s: str, k: int) -> int: char_count = Counter() max_string = 0 w_start = 0
for i in range(len(s)): char_count[s[i]] += 1 max_char = max(char_count.values())
if i - w_start + 1 - max_char > k: char_count[s[w_start]] -= 1 w_start += 1 else: max_string = max(max_string, i - w_start + 1)
return max_string
I personally think this code is easier to read.
ag
· 4 years ago
How do we apply sliding window approach for this leetcode question "LC 1763. Longest Nice Substring", I can do it brute force but unable to do it using sliding window approach.