-
-
Save bparanj/f8b5aef68dd156bafde2ee4bbf84019b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 1004: Max ConsecutiveOnes III | |
| maxLength = 0 | |
| numZeros = 0 | |
| # 1052: Grumpy Bookstore Owner | |
| maxCustWhenGrumpy = 0 | |
| idxOfStartX = 0 | |
| custWhenGrumpy = 0 | |
| # 1456: Max Number of Vowels in Substring of given length | |
| validVowels = {'a': True, 'e': True ,...} | |
| maxVowels = 0 | |
| vowelsInWindow = 0 | |
| # 424: Longest Repeating Character Replacement | |
| freq = {} | |
| maxWindowSize = 0 | |
| globalBest = 0 # variable that is updated during the grow phase | |
| windowStart = 0 # variable that tracks the start of the window | |
| # Custom data structures specific to the problem | |
| 1. frequency object. | |
| - if a key is present in the object. (is char a vowel) | |
| - How many keys are present in the object. (num different characters <= k) | |
| - What key is of max frequency in object. (# replacements == # that aren't max freq.) | |
| 2. Current variable count | |
| - How many elements in window meet criteria (numZeros in window) | |
| - At what point should the window start | |
| # Current Window length: 'end - start + 1' | |
| for end in (range(len(A))): | |
| # If manner of resetting start is winding up | |
| # Update variables given a constraint | |
| # If need to check the window is of certain size: | |
| # if end - start + 1 == goal: | |
| # If the problem is a "static sliding window" | |
| if end - start + 1 == size: | |
| # Shrink Operation | |
| # update variables | |
| start += 1 | |
| # Shrink Operation | |
| # Shrink window until the window is valid again | |
| - If problem is a "static sliding window" | |
| if end - start + 1 == size: | |
| # remove start element from variables | |
| start += 1 | |
| - shrinking window by 1 | |
| start += 1 | |
| - Shrink via "Wind" until the constraint is satisfied: | |
| while start != len(A) - 1 and not constraint: | |
| start += 1 | |
| - Reset window back to size 1: | |
| # If by looking ahead (element at end + 1) the variant is | |
| # broken, then "reset" the window back to a length of 1. | |
| start = end | |
| return globalBest |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment