longest_repeating_character_replacement

View Source

 1from collections import Counter
 2
 3
 4# @leet start
 5class Solution:
 6    def characterReplacement(self, s: str, k: int) -> int:
 7        """
 8        Given a string s, and an integer k, the amount of replacements
 9        allowed, we want to return the length of the longest string.
10        If we iterate through, we can add every char c one by one into our counter.
11        when len(counter) - max(counter) <= k, we have a valid max len
12        if we get to a state where that is not the case, we continue removing
13        characters from the beginning of our sliding window until we hit
14        the case where it is true again and increment our right pointer.
15        """
16        l = 0
17        c = Counter()
18        max_len = 0
19        for curr in s:
20            c[curr] += 1
21            while sum(c.values()) - max(c.values()) > k:
22                c[s[l]] -= 1
23                l += 1
24            max_len = max(max_len, sum(c.values()))
25
26        return max_len
27
28
29# @leet end
30
31
32def test():
33    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def characterReplacement(self, s: str, k: int) -> int:
 8        """
 9        Given a string s, and an integer k, the amount of replacements
10        allowed, we want to return the length of the longest string.
11        If we iterate through, we can add every char c one by one into our counter.
12        when len(counter) - max(counter) <= k, we have a valid max len
13        if we get to a state where that is not the case, we continue removing
14        characters from the beginning of our sliding window until we hit
15        the case where it is true again and increment our right pointer.
16        """
17        l = 0
18        c = Counter()
19        max_len = 0
20        for curr in s:
21            c[curr] += 1
22            while sum(c.values()) - max(c.values()) > k:
23                c[s[l]] -= 1
24                l += 1
25            max_len = max(max_len, sum(c.values()))
26
27        return max_len

def characterReplacement(self, s: str, k: int) -> int: View Source

 7    def characterReplacement(self, s: str, k: int) -> int:
 8        """
 9        Given a string s, and an integer k, the amount of replacements
10        allowed, we want to return the length of the longest string.
11        If we iterate through, we can add every char c one by one into our counter.
12        when len(counter) - max(counter) <= k, we have a valid max len
13        if we get to a state where that is not the case, we continue removing
14        characters from the beginning of our sliding window until we hit
15        the case where it is true again and increment our right pointer.
16        """
17        l = 0
18        c = Counter()
19        max_len = 0
20        for curr in s:
21            c[curr] += 1
22            while sum(c.values()) - max(c.values()) > k:
23                c[s[l]] -= 1
24                l += 1
25            max_len = max(max_len, sum(c.values()))
26
27        return max_len

Given a string s, and an integer k, the amount of replacements allowed, we want to return the length of the longest string. If we iterate through, we can add every char c one by one into our counter. when len(counter) - max(counter) <= k, we have a valid max len if we get to a state where that is not the case, we continue removing characters from the beginning of our sliding window until we hit the case where it is true again and increment our right pointer.

def test(): View Source

33def test():
34    assert 2 + 2 == 4