Grokking the Coding Interview: Patterns for Coding Questions
Vote

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

.....

.....

.....

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 2 replies
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 2 replies
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 2 replies
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%

Vote for new content