Sliding window | Leetcode

 https://leetcode.com/tag/sliding-window/

Sliding Window

Problems

Discuss

You have solved 29 / 92 problems.

Show problem tags

	#	Title	Acceptance	Difficulty	Frequency
	220	Contains Duplicate III	22.3%	Hard
	2156	Find Substring With Given Hash Value	22.4%	Hard
	862	Shortest Subarray with Sum at Least K	25.9%	Hard
	1044	Longest Duplicate Substring	30.5%	Hard
	30	Substring with Concatenation of All Words	31.4%	Hard
	2781	Length of the Longest Valid Substring	32.1%	Hard
	2528	Maximize the Minimum Powered City	33.0%	Hard
	2398	Maximum Number of Robots Within Budget	33.2%	Hard
	2106	Maximum Fruits Harvested After at Most K Steps	35.2%	Hard
	683	K Empty Slots	37.0%	Hard
	1610	Maximum Number of Visible Points	37.3%	Hard
	480	Sliding Window Median	40.4%	Hard
	2524	Maximum Frequency Score of a Subarray	40.4%	Hard
	76	Minimum Window Substring	41.0%	Hard
	1703	Minimum Adjacent Swaps for K Consecutive Ones	42.7%	Hard
	727	Minimum Window Subsequence	43.1%	Hard
	1499	Max Value of Equation	45.1%	Hard
	239	Sliding Window Maximum	46.1%	Hard
	1425	Constrained Subsequence Sum	47.7%	Hard
	995	Minimum Number of K Consecutive Bit Flips	51.3%	Hard
	2302	Count Subarrays With Score Less Than K	53.1%	Hard
	992	Subarrays with K Different Integers	55.3%	Hard
	632	Smallest Range Covering Elements from K Lists	61.5%	Hard
	2444	Count Subarrays With Fixed Bounds	61.8%	Hard
	2747	Count Zero Request Servers	31.3%	Medium
	2653	Sliding Subarray Beauty	31.7%	Medium
	2555	Maximize Win From Two Segments	32.0%	Medium
	3	Longest Substring Without Repeating Characters	33.9%	Medium
	2461	Maximum Sum of Distinct Subarrays With Length K	34.0%	Medium
	2516	Take K of Each Character From Left and Right	34.4%	Medium
	2730	Find the Longest Semi-Repetitive Substring	34.5%	Medium
	2779	Maximum Beauty of an Array After Applying Operation	35.2%	Medium
	1477	Find Two Non-overlapping Sub-arrays Each With Target Sum	36.6%	Medium
	1234	Replace the Substring for Balanced String	37.4%	Medium
	1658	Minimum Operations to Reduce X to Zero	37.6%	Medium
	1888	Minimum Number of Flips to Make the Binary String Alternating	39.2%	Medium
	2762	Continuous Subarrays	39.6%	Medium
	1838	Frequency of the Most Frequent Element	39.7%	Medium
	2411	Smallest Subarrays With Maximum Bitwise OR	42.4%	Medium
	904	Fruit Into Baskets	43.7%	Medium
	567	Permutation in String	44.2%	Medium
	1156	Swap For Longest Repeated Character Substring	44.7%	Medium
	395	Longest Substring with At Least K Repeating Characters	44.8%	Medium
	837	New 21 Game	45.4%	Medium
	1696	Jump Game VI	45.9%	Medium
	713	Subarray Product Less Than K	46.2%	Medium
	209	Minimum Size Subarray Sum	46.4%	Medium
	658	Find K Closest Elements	46.9%	Medium
	978	Longest Turbulent Subarray	47.2%	Medium
	187	Repeated DNA Sequences	47.4%	Medium
	340	Longest Substring with At Most K Distinct Characters	48.3%	Medium
	2090	K Radius Subarray Averages	48.3%	Medium
	1438	Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit	48.6%	Medium
	1839	Longest Substring Of All Vowels in Order	48.8%	Medium
	2537	Count the Number of Good Subarrays	49.0%	Medium
	1208	Get Equal Substrings Within Budget	49.3%	Medium
	2401	Longest Nice Subarray	49.7%	Medium
	487	Max Consecutive Ones II	49.8%	Medium
	438	Find All Anagrams in a String	50.3%	Medium
	2260	Minimum Consecutive Cards to Pick Up	50.8%	Medium
	718	Maximum Length of Repeated Subarray	51.2%	Medium
	2134	Minimum Swaps to Group All 1's Together II	51.4%	Medium
	1297	Maximum Number of Occurrences of a Substring	51.8%	Medium
	424	Longest Repeating Character Replacement	52.3%	Medium
	1423	Maximum Points You Can Obtain from Cards	52.3%	Medium
	1918	Kth Smallest Subarray Sum	52.6%	Medium
	930	Binary Subarrays With Sum	53.6%	Medium
	159	Longest Substring with At Most Two Distinct Characters	54.0%	Medium
	2107	Number of Unique Flavors After Sharing K Candies	55.8%	Medium
	1052	Grumpy Bookstore Owner	57.1%	Medium
	1695	Maximum Erasure Value	57.6%	Medium
	1456	Maximum Number of Vowels in a Substring of Given Length	58.2%	Medium
	1031	Maximum Sum of Two Non-Overlapping Subarrays	59.6%	Medium
	1151	Minimum Swaps to Group All 1's Together	60.8%	Medium
	1248	Count Number of Nice Subarrays	62.3%	Medium
	1004	Max Consecutive Ones III	63.0%	Medium
	1358	Number of Substrings Containing All Three Characters	64.0%	Medium
	1493	Longest Subarray of 1's After Deleting One Element	66.2%	Medium
	2024	Maximize the Confusion of an Exam	67.3%	Medium
	1343	Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold	68.0%	Medium
	1852	Distinct Numbers in Each Subarray	71.0%	Medium
	1100	Find K-Length Substrings With No Repeated Characters	74.6%	Medium
	2743	Count Substrings Without Repeating Character	77.3%	Medium
	2760	Longest Even Odd Subarray With Threshold	28.2%	Easy
	219	Contains Duplicate II	43.0%	Easy
	643	Maximum Average Subarray I	43.5%	Easy
	1176	Diet Plan Performance	52.9%	Easy
	1984	Minimum Difference Between Highest and Lowest of K Scores	55.0%	Easy
	2269	Find the K-Beauty of a Number	57.9%	Easy
	2379	Minimum Recolors to Get K Consecutive Black Blocks	57.9%	Easy
	1763	Longest Nice Substring	60.9%	Easy
	1876	Substrings of Size Three with Distinct Characters	71.7%	Easy

Find minimum substring given unique characters

 C# | Sliding window | July 2023 | Test cases | Warm up

jianminchen

774

7

20 hours ago

C#

Intuition

Approach

Complexity

• Time complexity:

O(m + n), m is length of string, n is length of pattern string.

• Space complexity:

Code

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _76_minimum_window_substring_review
{
    class Program
    {
        static void Main(string[] args)
        {
            var testResult = GetShortestUniqueSubstring(new char[] { 'a', 'b', 'c' }, "aaaefbcgaxy");
            Debug.Assert(testResult.CompareTo("bcga") == 0);
        }

        /// <summary>
        /// code review on July 19, 2023
        /// https://codereview.stackexchange.com/questions/176769/find-the-smallest-substring-that-contains-some-given-subset-of-characters
        /// </summary>
        /// <param name="search"></param>
        /// <param name="source"></param>
        /// <returns></returns>
        public static string GetShortestUniqueSubstring(char[] search, string source)
        {
            if (search == null || search.Length == 0 || string.IsNullOrEmpty(source))
            {
                return "";
            }

            // put unique chars in search string to the dictionary
            var map = new Dictionary<char, int>();
            var set = new HashSet<char>(search);

            foreach (var item in search)
            {
                map.Add(item, 1);
            }           

            // iterate the string and find match, and also keep track of minimum 
            var left = 0;
            var length = source.Length;

            var smallestLength = length + 1;
            var smallestSubstring = "";

            for (int index = 0; index < length; index++)
            {
                var visit = source[index];

                //var inMap = map.ContainsKey(visit);
                //var needOne = inMap && map[visit] > 0;

                if (map.ContainsKey(visit))
                {
                    map[visit]--;                   
                }

                set.Remove(visit);
                
                if (set.Count > 0)
                {
                    continue;
                }

                // move left point forward
                // extra one -> value in hashmap has negative value 
                while (left <= index && (!map.ContainsKey(source[left]) || map[source[left]] < 0))
                {
                    var removeChar = source[left];
                                     
                    if (map.ContainsKey(removeChar))
                    {
                        map[removeChar]++;
                    }

                    left++;
                }

                // added on July 19, 2023 - index-out-of-range concern
                if (left == length)
                {
                    break;
                }

                var currentLength = index - left + 1;                
                if (currentLength < smallestLength)
                {
                    smallestLength = currentLength;
                    smallestSubstring = source.Substring(left, currentLength);
                }

                var removed = source[left];
                map[removed]++;
                set.Add(removed);  // match map 

                left = left + 1;                                                               
            }

            return smallestLength == (length + 1) ? "" : smallestSubstring;            
        }
    }
}

Collar Example

Here is the article. 

The Collar Options Strategy Explained in Simple Terms

Collar Example

Assume an investor is long 1,000 shares of stock ABC at a price of $80 per share, and the stock is currently trading at $87 per share. The investor wants to temporarily hedge the position due to the increase in the overall market's volatility.

The investor purchases 10 put options (one option contract is 100 shares) with a strike price of $77 and a premium of $3.00 and writes 10 call options with a strike price of $97 with a premium of $4.50.

• Cost to implement collar (Buy $77 strike Put & write $97 strike call) is a net credit of $1.50 / share.
• Breakeven point = $80 + $1.50 = $81.50 / share.

The maximum profit is $15,500, or 10 contracts x 100 shares x (($97 - $1.50) - $80). This scenario occurs if the stock prices goes to $97 or above.

Conversely, the maximum loss is $4,500, or 10 x 100 x ($80 - ($77 - $1.50)). This scenario occurs if the stock price drops to $77 or below.

Flatten a Dictionary | C# | Warmup

 #Flatten a Dictionary

Given a dictionary, write a function to flatten it. Consider the following input/output scenario for better understanding:

Input:

{ 'Key1': '1', 'Key2': { 'a' : '2', 'b' : '3', 'c' : { 'd' : '3', 'e' : '1' } } } Output:

{ 'Key1': '1', 'Key2.a': '2', 'Key2.b' : '3', 'Key2.c.d' : '3', 'Key2.c.e' : '1' }

July 18, 2023
My C# practice
https://gist.github.com/jianminchen/98e6b3175a6d01d35c18b2f6f05011be

Hengrui Zhang

 Hengrui Zhang has 3 years of experience in public equity investment research & analysis with a focus on US and Asian markets. In his current role at Acuity Knowledge Partners, Hengrui supports investment management for a large Asia private equity fund, covering a wide spectrum of industries including but unlimited to healthcare, education, consumers, and real estate. Hengrui holds a bachelor’s degree in economics from the University of Toronto.

Author's Contribution

A collar strategy

 A collar is an options strategy that involves buying a downside put and selling an upside call that is implemented to protect against large losses, but that also limits large upside gains. The protective collar strategy involves two strategies known as a protective put and covered call.

Victor Sperandeo

 Victor Sperandeo, known as “Trader Vic”, is a US trader, index developer, and financial commentator based in Grapevine, Texas, United States. He serves as the President and CEO of Alpha Financial Technologies, LLC (AFT), is a founding partner of EAM Partners L.P., and serves as the President and CEO of its general partner, EAM Corporation.

Sperandeo traded in commodities, particularly in the energy and metals sectors. He is renowned for having 'predicted' the stock market crash of 1987 during an extensive interview in the September 21 issue of Barron's; on October 16, one trading session prior to Black Monday, Sperandeo shorted the Dow and made 300% during a day the DJIA fell by over 20%.^[2]