directory

• 424. The longest repeated character after replacement
• • Thinking analysis 1
  • To optimize the
• 1004. Maximum number of consecutive 1s III
• • Friendship remind
  • Method 1, based on the current maximum frequency
  • Method 2, based on the historical maximum frequency

424. The longest repeated character after replacement

Leetcode-cn.com/problems/lo… Given a string of only uppercase English letters, you can replace any character in any position with another character up to k times. After doing the above, find the length of the longest string that contains repeated letters.

Note: The string length and k cannot exceed 10^4. Example 1:

Input: s = “ABAB”, k = 2 Output: 4 Explanation: Replace two ‘A’ with two ‘B’, and vice versa.

Example 2:

Input: s = “AABABBA”, k = 1 Output: 4 Description: Replace the middle ‘A’ with ‘B’, and the string becomes “AABBBBA”. The substring “BBBB” has the longest repeated letter and the answer is 4.

Thinking analysis 1

class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0, right = 0;
        // The maximum frequency of elements in the current window
        int now_max_freq = 0;
        int hash_map[26] = {0};
        // Maximum window length
        int max_window_length = 0;
        while(right < s.size())
        {
            // Add the window element
            char c = s[right];
            // This element in the window corresponds to the frequency +1
            hash_map[c - 'A'] + +;// Find the maximum frequency within the window
            for(int i = 0; i < 26; i++)
                now_max_freq = max(now_max_freq,hash_map[i]);
            // If the maximum frequency + k >= the current window length, then we consider it meets the condition, then update the window length, take the larger value of the historical window length and the current window length
            if(now_max_freq + k >= right - left + 1)
            {
                max_window_length = max(max_window_length,right - left + 1);
            }
            // If the whole condition is not met, we need to pan the whole window
            else
            {
                char d = s[left];
                hash_map[d - 'A']--;
                left++;
            }
            right++;
        }
        returnmax_window_length; }};Copy the code

To optimize the

About optimization, first of all need to know that before we update window length conditions: 1, first find the maximum frequency within this window, if the frequency + 2 k > = the current window length, we choose to update the window length Because at the time of seeking maximum frequency have a process, and new to come in one character at a time we’ll have to compare the 26 times. (We can optimize the comparison, such as adding memos). But we don’t have to do that here. We just need to find the “maximum frequency of elements in the history window” and see if the frequency + k >= the current window length. If the maximum number of character repetitions in the current window is less than the maximum number of character repetitions in the history window, you can completely ignore the window, because it certainly cannot be the longest repeating substring. The maximum length of the history window is updated only when the maximum number of character repetitions is updated. Now we modify the above code slightly to the following:

class Solution {
public:
    int characterReplacement(string s, int k) {
        int left = 0, right = 0;
        // Maximum frequency in history
        int history_max_freq = 0;
        int hash_map[26] = {0};
        int max_window_length = 0;
        while(right < s.size())
        {
            // Add the window element
            char c = s[right];
            hash_map[c - 'A'] + +;// See if the entire element is the most common element in the window, if the value of history is updated
            history_max_freq = max(history_max_freq,hash_map[c - 'A']);
            if(history_max_freq + k >= right - left + 1)
            {
                max_window_length = max(max_window_length,right - left + 1);
            }
            else
            {
                char d = s[left];
                // If the window moves to the left, the frequency of the removed element in the window is -1
                hash_map[d - 'A']--;
                left++;
            }
            right++;
        }
        returnmax_window_length; }};Copy the code

The performance of the two solutions is quite different.



The next one is almost exactly the same thing, even if it’s a simplification, let’s do it both ways.

1004. Maximum number of consecutive 1s III

Friendship remind

Because of the simplicity of this problem, you’d better take a good look at the difference between the two codes before you assume they’re the same. (In fact, the performance should be similar, because there is no need to compare the current maximum frequency 26 times, only one time.)

Method 1, based on the current maximum frequency

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int left = 0, right = 0;
        int one_times = 0;
        int now_max_freq = 0;
        int max_window_length = 0;
        while(right < A.size())
        {
            int c = A[right];
            if(c == 1) one_times++;
            if(one_times + K >= right - left + 1)
            {
                max_window_length = max(max_window_length,right - left + 1);
            }
            else
            {
                int d = A[left];
                if(d == 1) one_times--;
                left++;
            }
            right++;
        }
        returnmax_window_length; }};Copy the code

Method 2, based on the historical maximum frequency

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int left = 0, right = 0;
        int one_times = 0;
        int history_max_freq = 0;
        int max_window_length = 0;
        while(right < A.size())
        {
            int c = A[right];
            if(c == 1) one_times++;
            history_max_freq = max(history_max_freq,one_times);
            if(history_max_freq + K >= right - left + 1)
            {
                max_window_length = max(max_window_length,right - left + 1);
            }
            else
            {
                int d = A[left];
                if(d == 1) one_times--;
                left++;
            }
            right++;
        }
        returnmax_window_length; }};Copy the code