Java 12 lines O(n) sliding window solution with explanation


  • 83
    J
        public int characterReplacement(String s, int k) {
            int len = s.length();
            int[] count = new int[26];
            int start = 0, maxCount = 0, maxLength = 0;
            for (int end = 0; end < len; end++) {
                maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
                while (end - start + 1 - maxCount > k) {
                    count[s.charAt(start) - 'A']--;
                    start++;
                }
                maxLength = Math.max(maxLength, end - start + 1);
            }
            return maxLength;
        }
    

    There's no edge case for this question. The initial step is to extend the window to its limit, that is, the longest we can get to with maximum number of modifications. Until then the variable start will remain at 0.

    Then as end increase, the whole substring from 0 to end will violate the rule, so we need to update start accordingly (slide the window). We move start to the right until the whole string satisfy the constraint again. Then each time we reach such situation, we update our max length.


  • 132
    T

    This solution is great, best so far. However, it requires a bit more explanation.

    Since we are only interested in the longest valid substring, our sliding windows need not shrink, even if a window may cover an invalid substring. We either grow the window by appending one char on the right, or shift the whole window to the right by one. And we only grow the window when the count of the new char exceeds the historical max count (from a previous window that covers a valid substring).

    That is, we do not need the accurate max count of the current window; we only care if the max count exceeds the historical max count; and that can only happen because of the new char.

    Here's my implementation that's a bit shorter

    public int characterReplacement(String s, int k)
    {
        int[] count = new int[128];
        int max=0;
        int start=0;
        for(int end=0; end<s.length(); end++)
        {
            max = Math.max(max, ++count[s.charAt(end)]);
            if(max+k<=end-start)
                count[s.charAt(start++)]--;
        }
        return s.length()-start;
    }

  • 0

    @tsuvmxwu great solution!


  • 9
    E

    @Joshua924
    The solution is great, but I have a small question here :
    when you move the start pointer, why we the max count may change:
    for example :
    s = "bbcdef", k = 2.
    when move end to 'e', we need to remove first 'b' so that maxcount will change to 1.
    But for s = "bbcdd", it wont change when we move end to second 'd' and remove first 'b'.
    In this question we may don't need to worry about that because we just need to get maxlength of substring. But what if the question is to find all the strategy, can we try to use similar method ?


  • 0

    great solution! How can you think of such a method


  • 1

    @emmonenirvana when move the left begin of b, maxcount will not be change to 1.It will always the biggest one unless another one is more than it. That is why explain that

    our sliding windows need not shrink, even if a window may cover an invalid substring

    this situation it will shift the whole window to the right by one


  • 1
    J

    @emmonenirvana The answer is yes. If you want to keep the variable maxCount up to date, you can have a priority queue that's sorted by count of each character. Then when you remove a character, you can update count in that queue, then poll the queue for new maxCount. In that case you will be able to reach the farthest every time you try to shift end.


  • 0
    D
    This post is deleted!

  • 1
    E

    @zhangCabbage ya I got your idea. It is a greedy solution.


  • 0
    E

    @Joshua924 Awesome ! thanks for your solution.


  • 0
    Z

    Pretty easy to understand. Thanks very much!


  • 7
    public class Solution {
        public int characterReplacement(String s, int k) {
            char[] sc = s.toCharArray();
            int[] count = new int[26];
            int maxCount = 0, start = 0;
            for(int i=0;i<sc.length;i++){
                int index = sc[i]-'A';
                count[index]++;
                maxCount = Math.max(maxCount, count[index]);
                // i - start means the current longest length, if the (maxCount + k) <= (the current longest length), we move whole windows right.
                // otherwise the start stays at current position, but the "i" moves, means next round the longest length will increase.
                if(maxCount + k <= i - start){
                    int indexStart = sc[start] - 'A';
                    count[indexStart]--;
                    start++;
                }
            }
            
            return sc.length-start;
        }
    }

  • 22
    K

    @tsuvmxwu Allow me to expand on your explanation:

    Basics:

    • We use a window.
    • The window starts at the left side of the string and the length of the window is initialized to zero.
    • The window only stays the same or grows in length as the algorithm proceeds.
    • The algorithm grows the window to the maximum valid length according to the rules of the game.
    • The algorithm returns the length of the window upon completion.

    Setup:

    • The length of the window is defined by the following equation: end - start + 1.
    • The values of both start and end are subject to change during the execution of the algorithm.
    • The value of end starts at 0 and gets incremented by 1 with each execution of the loop.
    • But unless a certain condition is met, the value of start will also gets incremented with each execution of the loop, keeping the length of the window unchanged.
    • That condition is met when the number of the most commonly occuring character in the window + k is at least as large as the length of the window (the value of k determines how many of the less commonly occurring characters there can be). This condition would be required to create a string containing all the same characters from the characters contained within the window.

    Execution:

    • Right in the beginning, the length of the window is going to be able to grow to at least the value of k.
    • After that initial growth, the algorithm becomes a search to find the window that contains the greatest number of reoccurring characters.
    • Whenever including the character at end results in an increase in the greatest number of reoccurring characters ever encountered in a window tested so far, the window grows by one (by not incrementing start).
    • When determining whether or not including another character at the end of the window results in the increase described above, only the occurrence of the newly included character in the window and the running all-time max need to be taken into account (after all, only the frequency of the newly included character is increasing).
    • Even if/when the value of start is incremented (i.e. the left side of the window is moved to the right), the all-time max doesn't need to be reset to reflect what's currently in the window because 1) at this point in the algorithm, the all-time maximum number of reoccurring characters in a window is what we're using to determine the all-time longest window; and 2) we only care about positive developments in our search (i.e. we find a window that contains an even greater number of reoccurring characters than any other window we have tested so far and therefore is longer than any window we have tested so far). The algorithm becomes a search for the max and we only need to set the max when we have a new max.

  • 1

    @tsuvmxwu @knowledge2thepeople
    rewrote the code in a more concise way, the idea is simple and smart!

        public int characterReplacement(String s, int k) {
            int[] count = new int[128];
            int start = 0, end = 0, max = 0;
            for ( ; end < s.length(); end++) {
                max = Math.max(max, ++count[s.charAt(end)]);
                if (max + k <= end - start) {count[s.charAt(start++)]--;}
            }
            return s.length() - start;
        }
    

    but why

    max + k <= end - start
    //instead of max + k < end - start ?
    

  • -2
    Z

    @tsuvmxwu great explanation!

    One comment is, s.length() - start = max + k in the end, but seems to me it's easier to understand if we return max + k instead, which is directly the result desired. Not sure if I miss anything.


  • 0
    K
    This post is deleted!

  • 5

    @Lara
    I think the orignial "end - start + 1 - maxCount > k" seems to be more undertandable. In this case, "end - start + 1" denotes the size of current window "- maxCount" means we edit all characters that are not the character for maxCount to the max character. This process will takes up "end - start + 1 - maxCount" steps. That's where the expression comes from. This is the same as "max + k <= end - start" mathematically. "end - start" will be the difference between indexs while "end - start + 1" will be the size.

    Hope the explanation helps.


  • 0
    S

    My thought is when we keep expand the window as possible as we can and once the window equal to the max + k == end - start
    next iteration end will be end + 1, that's why we want to add start

    public class Solution {
        // sliding window problem
        public int characterReplacement(String s, int k) {
            int st = 0;
            int max = 0;
            char [] count = new char [128];
            for (int end = 0; end < s.length(); end++) {
                max = Math.max(max, ++count[s.charAt(end)]);
                int window = end - st;
                if (max + k == window){
                    count[s.charAt(st++)] --;
                    
                }
                
            }
            return s.length() - st;
        }
    }

  • 0
    G

    @yzj1212 jj bursted to sky


  • 9
    J

    Awesome solution, but it needs some more detailed explanation.
    Many people know the problem can be reiterated as :
    "longest substring where (length - max occurrence) <= k"
    The key point is we are focusing on "longest".
    So assume we initially found a valid substring, what do we do next?

    1. Still valid even appended by one more char——then we are happy, just expand the window
    2. It became invalid. But at this time, do we have to shrink the window?
      ——No, we shift the whole window rightwards by one unit. So that the length is unchanged.
      The reason for that is , any index smaller than original "start", will never have the chance to lead a longer valid substring than current length of our window.
    3. Do we need to update max in time?
      ——No. Once again, we focus on "longest". The length of valid substring is determined by what?
      Max Occurrence + k
      We only need to update max occurrence when it becomes larger, because only that can we generate a longer valid substring.
      If we can't surpass the historic max occurrence, then we can not generate a longer valid substring from current "start", I mean the new windows's left bound. To some extend, this becomes a game to find max occurrence.
      Or , a better understanding is:
      "A game to eliminate inferior 'left bounds'.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.