424.Longest Repeating Character Replacement

Tags: [sliding_window], [map]

Link: https://leetcode.com/problems/longest-repeating-character-replacement/?tab=Description

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Solution: sliding_window, map

class Solution(object):
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if not s:
            return 0

        char_arr = list(s)
        max_len_of_substr = 0
        max_num_of_same_chars = 0
        char_map = {}

        start = 0
        end = 0
        while end < len(char_arr):
            curr = char_arr[end]
            if curr in char_map:
                char_map[curr] += 1
            else:
                char_map[curr] = 1
            max_num_of_same_chars = max(max_num_of_same_chars, char_map[curr])

            while (end - start + 1) - max_num_of_same_chars > k:
                # (end - start + 1) is the number of the chars in the current substring.
                # (end - start + 1) - max_num_of_same_chars is the min number of the different chars in the current substring.

                # shrink the window, moving the start to right
                char_map[char_arr[start]] -= 1
                start += 1

                # update the max_num_of_same_chars
                max_num_of_same_chars = 0
                for key in char_map:
                    max_num_of_same_chars = max(max_num_of_same_chars, char_map[key])

            sub_len = end - start + 1
            max_len_of_substr = max(max_len_of_substr, sub_len)
            end += 1

        return max_len_of_substr

Revelation:

• When we meet the problem about the string and substring, we can first try to think about the sliding_window solution.

Note:

• Time complexity = O(n), n is the number of characters in the given string. the process for updating the max_num__of_same__chars will cost T = O(1), because there at most 26 characters.

Time Limited Exceeded

class Solution(object):
    def characterReplacement(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        if not s:
            return 0

        char_arr = list(s)
        char_set = set(char_arr)
        return self.char_replacement_helper(char_arr, 0, k, char_set)

    def char_replacement_helper(self, char_arr, index, k, char_set):
        # base case
        if k == 0 or index >= len(char_arr):
            return self.max_len_repeated_substr(char_arr)

        # do not replace the char_arr[index]
        max_len = self.char_replacement_helper(char_arr, index + 1, k, char_set)

        # replace the char_arr[index]
        for c in char_set:
            if c == char_arr[index]:
                continue
            old_char = char_arr[index]
            char_arr[index] = c
            max_len = max(max_len, self.char_replacement_helper(char_arr, index + 1, k - 1, char_set))
            char_arr[index] = old_char

        return max_len

    @staticmethod
    def max_len_repeated_substr(char_arr):
        if not char_arr:
            return 0

        max_len = 0
        prev = None
        sub_len = 0
        for c in char_arr:
            if not prev:
                prev = c
                sub_len = 1
                continue

            if prev != c:
                max_len = max(max_len, sub_len)
                prev = c
                sub_len = 1
            else:
                prev = c
                sub_len += 1

        return max(max_len, sub_len)

Revelation:

• Brute-force: try all possible ways to replace or not replace the chars in the given string.

Note:

• Time complexity = T = O(2^n), n is the number of the chars in the given string. Explanation: for each char, we can choose between replacing this char or not replacing this char, which means for each char we have two paths. And if we replace the char, there are at most (26 - 1) ways to replace it, which is a consistent number.