Leetcode discuss: 424. Longest Repeating Character Replacement

March 8, 2022

Here is the link. 

C# | Sliding window technique | Time complexity: O(N)

Feb. 28, 2022
Introduction
It is most important to get optimized time complexity, linear complexity. I continued to modify the code after my last practice.

Two changes | One is to get max ocurrence in O(1) time | Always move right pointer
For every sliding window, it takes O(1) time to get max occurrence. Just use one variable maxValue and a HashMap.

Always move right pointer in every iteration seen in while statement.

In theory | after careful review
It is not a problem to move left pointer in sliding window, even though it may affect maxValue variable which stands for maxium occurrence in sliding window.

What if max frequent letters are more than one, the one recorded is not the same one removed. But it should still work, I should find a few test cases to explain in detail later if I have time.

Follow up
March 1, 2022
If the left pointer in sliding window increments one, the string in sliding window is a substring of previous sliding window, therefore there is no need to check max occurrence. In other words, right pointer can increment one as well. So inside while loop, every iteration the right pointer can increment one.

The following C# code passes online judge.

public class Solution {
    public int CharacterReplacement(string s, int k)
        {
            if (s == null || s.Length == 0 || k < 0)
                return 0;

            var length = s.Length;
            var left = 0;
            var right = 0;

            var map = new Dictionary<char, int>();
            var maxValue = 0; 
            var maxLength = 0;            

            while (left <= right && right < length)
            {                
                var current = s[right];

                if (!map.ContainsKey(current))
                {
                    map.Add(current, 0);
                }

                map[current]++;         

                /* the following two statements: Time complexity: O(NlogN)
                var values = map.Values.ToList();
                var maxValue = values.Max();
                */
                maxValue = map[current] > maxValue? map[current] : maxValue;

                var width = right - left + 1;
                var widthCheck = width - maxValue <= k;
                if (widthCheck)
                {
                    maxLength = width > maxLength ? width : maxLength;
                   // right++;
                }
                else
                {
                    var removed = s[left];
                    map[removed]--;
                    if (map[removed] == 0)
                    {
                        map.Remove(removed);
                    }

                    left++;
                }

                // always move right pointer
                right++;
            }

            return maxLength;
        }
}