Grokking the Engineering Manager Coding Interview
Vote

0% completed

​

Solution: Longest Substring with Same Letters after Replacement

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

.....

.....

.....

Like the course? Get enrolled and start learning!
Ankit Joshi

Ankit Joshi

· a year ago

For given test case

"aaaaa"

0

When doing run expected value is 0, while in submit expected value is 5

Show 1 reply
S

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

Show 1 reply
S

sean.maginnis.sm

· 2 years ago

Your Input

"abcd" 2 Output 3 Expected 2

you can replace any 2 characters

so abcd ===> aaad or abbb or accc or addd which would be 3 not 2

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLength(self, text, k):
      max_length = float('-inf')
      freq = {}
      j = 0 
      
      most_freq_char = float('-inf')

      for i in range(len(text)):
        # update all characters frequencies
        char = text[i]
        freq[char] = freq.get(char, 0)
        freq[char] += 1

        # track the most frequent character 
        most_freq_char = max(most_freq_char, freq[char])

        # total_len = the total length of the window 
        # can_be_discarded_len = the length of the characters other than the most frequent character 
        # can_be_discarded_len is what we use for knowing <= or > k 
        total_len = i - j + 1
        can_be_discarded_len = total_len - most_freq_char
        
        if can_be_discarded_len <= k:
Geraud KAMENI

Geraud KAMENI

· 2 years ago

#The solution provide is incorrect, do not calculate max_lenght in invalid windows, add else condition
# Current window size is from window_start to window_end, overall we have a letter
            # which is repeating 'max_repeat_letter_count' times, this means we can have a window
            # which has one letter repeating 'max_repeat_letter_count' 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 (window_end - window_start + 1 - max_repeat_letter_count) > k:
                left_char = str1[window_start]
                frequency_map[left_char] -= 1
                window_start += 1
A

ahonliu

· 2 years ago

When the window shrinks, it is possible that maxRepeatLetterCount reduces, right?

Show 4 replies
P

Popa Stefan

· 3 years ago

So for the following input:

"aba"

1

The expected output is 1!

Unless there is something I don't understand, by replacing the one b with an a we should have an expected value of 3 (aaa)

Show 3 replies
A

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.

Show 1 reply
S

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.

A

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.

Reading Progress

0%