C# - different approach - find ranges - O(n)


  • 0

    Here is a little different approach than the sliding window solution that is no doubt the most efficient, but this one's interesting so thought I'd offer it up. The idea is that you can do a 1 pass scan to compile a list of ranges for each character. A range list is a list of start/end pairs for each character. I use a map (array) to hold the list and just add ranges as I scan the string. Once the ranges are compiled I go through each list of ranges and determine, based on the gap between ranges, how long a total range can be formed. This is a greedy pass so all total the solution is O(n) time with O(n) memory.

    public class Solution {
        public int CharacterReplacement(string s, int k) 
        {
            // build ranges
            List<Range>[] map = new List<Range>[26];
            for (int i = 0; i < 26; i++) map[i] = new List<Range>();
            for (int i = 0; i < s.Length; i++)
            {
                List<Range> ranges = map[s[i]-'A'];
                if (i == 0 || s[i] != s[i-1]) ranges.Add(new Range(i,i));
                else ranges[ranges.Count-1].end = i;
            }
            
            // look for max
            int max = 0;
            foreach (List<Range> ranges in map.Where(x => x.Count > 0))
            {
                int used = 0;
                int left = 0;
                int right = 0;
                while (right < ranges.Count)
                {
                    // used too many - advance left
                    while (used > k)
                    {
                        left++;
                        used -= ranges[left].start - ranges[left - 1].end - 1;
                    }
    
                    // calc length and add as much of the unused swaps as you can depending 
                    // the available space before and after the range
                    int len = ranges[right].end - ranges[left].start + 1;
                    int padding = ranges[left].start + s.Length - ranges[right].end - 1;
                    len += Math.Min(k-used, padding);
                    max = Math.Max(max, len);
                    
                    // next iteration - advance right
                    right++;
                    if (right < ranges.Count) used += ranges[right].start - ranges[right-1].end - 1;
                }
            }
    
            return max;
        }
    }
    
    public class Range
    {
        public int start;
        public int end;
        public Range(int s, int e) { start = s; end = e; }
    }
    

Log in to reply
 

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