[LeetCode] Longest Subarray of 1's After Deleting One Element

Problem: Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Approach: This problem is similar to problem of maximum number of consecutive 1's in the array if you can flip at most k 0's. Here is k is constant which is 1 so here too we are going to take sliding window approach and answer is the max window size - 1.

Implementation in C#:

    public int LongestSubarray(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int start = 0, end = 0, k = 1;

        for (; end < length; ++end)

        {

            if (nums[end] == 0)

            {

                --k;

            }

            if (k < 0)

            {

                if (nums[start++] == 0)

                {

                    ++k;

                }

            }

        }

        return end - start - 1;

    }

Complexity: O(n)

[LeetCode] Max Consecutive Ones III

Problem: Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Approach: This is kind of again a sliding window problem but here the window size is not constant. The window size can be expanded till the condition is satisfied which is the window must have at most k 0's.

We can expand the window till the above condition is satisfied i.e. we keep increasing the end but when we see the window has k + 1 0's, we start shrinking the window from the left i.e. we keep increasing start till we get nums[start] = 0. To reduce this iteration we can use queue to store the indices of all 0's so that we can directly jump to back of queue + 1 index to find the next start. At any point of time the current window size would be end - start.

If you see from the above approach we would be able to solve this problem in linear time but we are taking extra storage. Off course we can remove this extra storage but in that case we might end up doing 2 * n steps. Anything else we can do to improve it further? 

Just think whenever current window can be expanded i.e. window has at most k 0's, start doesn't move and in the end the max distance is really end - start. Means in case of k + 1 0's we keep increasing the start and end is anyway alwasy increasing. So even if we don't reach the 0 to shrink the window the size of the remains same till the above condition is not satisfied because we keep incrementing start by 1 at every step.

That's all

Implementation in C#:

With Queue:

    public int LongestOnes(int[] nums, int k)

    {

        int length  = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        Queue<int> zeroIndicesQ = new Queue<int>();

        int maxLength = 0, start = 0;

        bool isFirstZero = true;

        for (int i = 0; i < length; ++i)

        {

            if (nums[i] == 0)

            {

                zeroIndicesQ.Enqueue(i);

                --k;

                if (k < 0)

                {

                    k = 0;

                    maxLength = maxLength < i - start ?

                                i - start :

                                maxLength;

                    start = zeroIndicesQ.Dequeue() + 1;

                }

            }

        }

        return maxLength < length - start ?

               length - start :

               maxLength;

    }

Optimized way:

        public int LongestOnes(int[] nums, int k)

    {

        int length  = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int start = 0, end = 0;

        for (; end < length; ++end)

        {

            if (nums[end] == 0)

            {

                --k;

            }

            if (k < 0)

            {

                if (nums[start] == 0)

                {

                    ++k;

                }

                ++start;

            }

        }

        return end - start;

    }

Complexity: O(n)

[LeetCode] Maximum Number of Vowels in a Substring of Given Length

Problem: Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Example:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Approach: We can take all the substring of size k of given string s and can check the number of vowels in those substrings and then we can return the maximum of all those counts but that will be time consuming task. 

We can use sliding window approach here to solve this problem. Obviously the size of the window here will be k. First we take the first k characters of s and count the number of vowels in it. Now we slide this k sized window one by one. The vowel count of the sliding window will be modified as follows:

curr_vowel_count =  curr_vowel_count - IsVowel(s[start]) + IsVowel(s[curr_index])

Here the curr_index is the end of the window and start is obviously the start of the window.

Implementation in C#:

        public int MaxVowels(string s, int k)

    {

        int length = s?.Length ?? 0;

        if (length < k)

        {

            return 0;

        }

        int currVowelCount = 0, i = 0;

        for (; i < k; ++i)

        {

            if (this.IsVowel(s[i]))

            {

                ++currVowelCount;

            }

        }

        int start = 0, maxVowelCount = currVowelCount;

        for (; i < length; ++i)

        {

            if (this.IsVowel(s[start++]))

            {

                --currVowelCount;

            }

            if (this.IsVowel(s[i]))

            {

                ++currVowelCount;

                maxVowelCount = maxVowelCount < currVowelCount ?

                                currVowelCount :

                                maxVowelCount;

            }

        }

        return maxVowelCount;

    }

    private bool IsVowel(char ch)

    {

        return ch == 'a' ||

               ch == 'e' ||

               ch == 'i' ||

               ch == 'o' ||

               ch == 'u';

    }

Complexity: O(n)

[LeetCode] Maximum Average Subarray I

Problem: You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10^-5 will be accepted.

Example:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Input: nums = [5], k = 1
Output: 5.00000

Constraints:

• n == nums.length
• 1 <= k <= n <= 10^5
• -10^4 <= nums[i] <= 10^4

Approach: This is clearly a sliding window problem. We can take sum of first k elements say 'sum' and then we slide the window by one i.e. remove first element of window from sum and add new element of the slided window to sum and record the max sum so far so every step looks like:

• sum = sum - nums[start] + nums[i] 
• start++
• max_sum = MAX(sum, max_sum)

Implementation in C#:

        public double FindMaxAverage(int[] nums, int k)

    {

        int length = nums?.Length ?? 0;

        if (length < k)

        {

            return 0;

        }

        long sum = 0;

        int i = 0, start = 0;

        for (; i < k; ++i)

        {

            sum += nums[i];

        }

        long maxSum = sum;

        for (i = k; i < length; ++i)

        {

            sum = sum - nums[start++] + nums[i];

            maxSum = sum > maxSum ? sum : maxSum;

        }

        return (double)maxSum / k;

    }

Complexity: O(n)

[Google][GeeksForGeeks] Longest substring with k unique characters

Problem: Given a string you need to return longest possible substring that has exactly K unique characters. If there is more than one substring of longest possible length, then print any one of them. If there are no such substring, return empty string.

Example:

Input: str = "aabbcc", k = 2
Output: "aabb"
Explanation: Can return "bbcc"

Approach: This is a straight forward sliding window problem. We can use a map to maintain the characters and their count in the current window. Whenever the number of keys in the map are equal to the k, we can check if current window length is more than max length then we can update the max length.

if length of current window is more than k then we need to slide the window from the left. That's all!

Implementation in C#:

    private static string MaxSubstringWithKUniqueChars(string str, int k)

    {

        int length = str?.Length ?? 0;

        if (length < k)

        {

            return "";

        }     

        Dictionary<char, int> freqMap = new Dictionary<char, int>(); 

        int start = 0, maxLength = 0, startIndex = -1;

        for (int end = 0; end < length; ++end)

        {

            if (!freqMap.ContainsKey(str[end]))

            {

                freqMap[str[end]] = 0;

            }

            ++freqMap[str[end]];

            if (freqMap.Count == k)

            {

                int currLength = end - start + 1;

                if (maxLength < currLength)

                {

                    maxLength = currLength;

                    startIndex = start;

                }

            }

            while (freqMap.Count > k)

            {

                --freqMap[str[start]];

                if (freqMap[str[start]] == 0)

                {

                    freqMap.Remove(str[start]);

                }

                ++start;

            }

        }

        return startIndex != -1 ? str.Substring(startIndex, maxLength) : "";

    }

Complexity: O(n)

[Google][LintCode] Longest Substring with At Most K Distinct Characters

Problem: Given a string S, find the length of the longest substring T that contains at most k distinct characters.

Example:

Input: S = "eceba", k = 2
Output: 3 ("ece")

Input: S = "aa", k = 1
Output: 2 ("aa")

Approach: We will use Sliding Window approach here. We will increase the window till the number of unique characters in window is less than k. Obviously we will use a map here to keep track of it. We will also keep tracking of the max length by comparing the maxLength variable to the current window length.

Implementation in C#:

    public int LengthOfLongestSubstringKDistinct(string s, int k)

    {

        int start = 0, end = 0, maxLength = 0;

        Dictionary<char, int> charFreqMap = new Dictionary<char, int>();

        while (end < s.Length)

        {

            if (!charFreqMap.ContainsKey(s[end]))

            {

                charFreqMap[s[end]] = 0;

            }

            ++charFreqMap[s[end]];

            while (charFreqMap.Keys.Count > k)

            {

                --charFreqMap[s[start]];

                if (charFreqMap[s[start]] == 0)

                {

                    charFreqMap.Remove(s[start]);

                }

                ++start;

            }

            maxLength = Math.Max(maxLength, end - start + 1);

            ++end;

        }

        return maxLength;

    }

Complexity: O(n)

Minimum Size Subarray Sum

Problem: Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

Input: s = 12, nums = [2,3,1,5,8,3]
Output: 2
Explanation: the subarray [5,8] has the minimal length under the problem constraint.

Approach: Keep 2 pointers, one for the start and another for the end of the current subarray and make optimal moves so as to keep the sum greater than s as well as maintain the lowest size possible. Here are the steps which we can follow:

• Initialize startIndex to 0, currSum to 0 and result to INT_MAX.
• Foreach i where i = 0 to n:
• Add array[i] to currSum 
• WHILE currSum >= s
• result = MIN (result, i - startIndex + 1); // min of result and length of current sub array
• At this point we can safely increment the startIndex as min subarray starting with this index where currSum >= s is found already.
• currSum -= array[startIndex]
• startIndex += 1

Now we can return result if it is not INT_MAX otherwise 0.

Implementation in C#:

    public int MinSubArrayLen(int target, int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        int minLength = int.MaxValue;

        int start = 0;

        int currSum = 0;

        for (int end = 0; end < length; ++end)

        {

            currSum += nums[end];

            while (currSum >= target)

            {

                minLength = Math.Min(minLength, end - start + 1);

                currSum -= nums[start++];

            }

        }

        return minLength == int.MaxValue ? 0 : minLength;

    }

Complexity: O(n)

[Uber][LeetCode] Minimum Window Substring

Problem: Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Approach: 

1. First check if the length of string is less than the length of the given pattern, if yes then return empty string.
2. Store the occurrence of characters of the given pattern in a hash.
3. Start matching the characters of pattern with the characters of string i.e. increment count if a character matches.
4. Check if (count == length of pattern ) this means a window is found.
5. If such window found, try to minimize it by removing extra characters from the beginning of the current window.
6. Update minWindowLength.
7. Return the minimum length window.

Implementation in C#:

    public string MinWindow(string s, string t)

    {

        int sLength = s?.Length ?? 0;

        int tLength = t?.Length ?? 0;

        if (sLength < tLength)

        {

            return "";

        }

        var tCharMap = this.BuildCharMap(t);

        var sCharMap = new Dictionary<char, int>();

        int count = 0;

        int startIndex = -1, start = 0, minLen = int.MaxValue;

        for (int end = 0; end < sLength; ++end)

        {

            if (!sCharMap.ContainsKey(s[end]))

            {

                sCharMap[s[end]] = 0;

            }

            ++sCharMap[s[end]];

            if (tCharMap.ContainsKey(s[end]) &&

                sCharMap[s[end]] <= tCharMap[s[end]])

            {

                ++count;

            }

            if (count == tLength)

            {

                while (!tCharMap.ContainsKey(s[start]) ||

                       tCharMap[s[start]] < sCharMap[s[start]])

                {

                    --sCharMap[s[start]];

                    ++start;

                }

                int currLen = end - start + 1;

                if (currLen < minLen)

                {

                    minLen = currLen;

                    startIndex = start;

                }

            }

        }

        if (startIndex == -1)

        {

            return "";

        }

        return s.Substring(startIndex, minLen);

    }

    private Dictionary<char, int> BuildCharMap(string str)

    {

        var charMap = new Dictionary<char, int>();

        foreach (char ch in str)

        {

            if (!charMap.ContainsKey(ch))

            {

                charMap[ch] = 0;

            }

            ++charMap[ch];

        }

        return charMap;

    }

Complexity: O(n)

[LeetCode] Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Approach: Clearly it's a sliding window problem. Like in any other sliding window problem we will maintain start and end indices of current window. We can have a hash map but we can use hash set here as the occurrence of  every character in substring can't be more than one. We will keep incrementing end by 1 and for each index 'end', there could be 2 cases:

1. s[end] is not in current window means it won't be in our hash set too. We can simply add s[end] to hash set i.e. add s[end] to current window. We will also see if the current window length is more than max length then we can assign current length to max length.
2. s[end] is already in current window means it is already in our hash set. In this case we need to slide our window from the left. Means we will keep increasing start index of window and keep removing s[start] from hash set until s[end] character is removed from the hash set / current window.

In the end we will just return the max length. That's all!

Implementation in C#:

    public int LengthOfLongestSubstring(string s)

    {

        int length = s?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        HashSet<char> charSet = new HashSet<char>();

        int start = 0;

        int end = 0;

        int maxLen = 0;

        for ( ; end < length; ++end)

        {

            if (charSet.Contains(s[end]))

            {

                maxLen = Math.Max(maxLen, end - start);

                while (charSet.Contains(s[end]))

                {

                    charSet.Remove(s[start++]);

                }

            }

            charSet.Add(s[end]);

        }

        return Math.Max(maxLen, end - start);

    }

Complexity: O(n)