Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Longest Substring with Same Letters after Replacement

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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:
A

Anonymous

· 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

Anonymous

· 2 years ago

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

A

Anonymous

· 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 1 reply
A

Anonymous

· 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
A

Anonymous

· 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

Anonymous

· 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.

A

Anonymous

· 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

Show 1 reply
A

Anonymous

· 4 years ago

Hard problems should come with a visual component, often times just writing a paragraph explanation will not suffice.

A

Anonymous

· 5 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?

Show 1 reply

Reading Progress

0%

Vote for new content