Sliding Window Flashcards
- Longest Substring Without Repeating Characters
Solved
Medium
Topics
Companies
Hint
Given a string s, find the length of the longest
substring
without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
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.
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
l = 0
r = 0
winset = set()
longest = 0
while r < len(s):
if s[r] not in winset:
winset.add(s[r])
longest = max(longest, r-l+1)
else:
while s[l] != s[r] and l < r:
winset.remove(s[l])
l+=1
l+=1
r += 1
return longest- Longest Repeating Character Replacement
Solved
Medium
Topics
Companies
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.
Example 2:
Input: s = “AABABBA”, k = 1
Output: 4
Explanation: Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.
The substring “BBBB” has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.
Constraints:
1 <= s.length <= 105
s consists of only uppercase English letters.
0 <= k <= s.length
https://leetcode.com/problems/longest-repeating-character-replacement/
the reason we do not update maxfrequency is because we always extend the right pointer and keep incrementing the left if the window is invalid. the only way for the window to become valid is to find some character with more frequency than the maxfreq without more than k characters in between its occurances. Thus maxfrequency can remain the same and still help to decide if window is valid or not.
from collections import defaultdict
class Solution(object):
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
charmap = defaultdict(int)
l = 0
r = 0
maxfreq = 0
maxlen = 0
while r < len(s):
charmap[s[r]] += 1
maxfreq = max(maxfreq, charmap[s[r]])
windowlen = r - l + 1
if windowlen - maxfreq > k:
charmap[s[l]] -= 1
l += 1
# window is either valid or is not greater than the last largest window seen.
maxlen = max(maxlen, r - l + 1)
r+=1
return maxlen
o(nk) solution more intuitive because it keeps track of max values.
from collections import defaultdict
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
l = 0
window = set()
charmap = defaultdict(int)
max_len = 1
for r in range(len(s)):
charmap[s[r]] += 1
while (r-l+1)-max(charmap.values()) > k and l<r:
charmap[s[l]] -= 1
l += 1
max_len = max(r-l+1, max_len)
return max_len- Permutation in String
Companies
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1’s permutations is the substring of s2.
Example 1:
Input: s1 = “ab”, s2 = “eidbaooo”
Output: true
Explanation: s2 contains one permutation of s1 (“ba”).
Example 2:
Input: s1 = “ab”, s2 = “eidboaoo”
Output: false
Constraints:
1 <= s1.length, s2.length <= 104
s1 and s2 consist of lowercase English letters.
https://leetcode.com/problems/permutation-in-string/description/
as you add and remove characters, update the map representing the window and compare s1 map and s2 map. The following solution uses a variable tracking the number of matches imagining if both strings had all characters but with count 0
Sliding window, window size fixed at the s1 size.
Neetcode video explains. not medium problem to solve in O(n) would consider Hard
from collections import defaultdict
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
# Start with s2 map being generated from first len(s1) characters of s1
s1_map = defaultdict(int)
s2_map = defaultdict(int)
for i in range(len(s1)):
s1_map[s1[i]] += 1
s2_map[s2[i]] += 1
matches = 0
for i in range(26):
character = chr(i + ord('a'))
if s1_map[character] == s2_map[character]:
matches += 1
l = 0
for r in range(len(s1), len(s2)):
# we may have found match in the first window itself, check.
if matches == 26:
return True
# Starting at window size + 1 (so imagine we are now taking our first right step)
# Add the right in s2 map and check
s2_map[s2[r]] += 1
# If we get to same as s1 increment matches, ( we will deal with removing left later)
if s2_map[s2[r]] == s1_map[s2[r]]:
matches += 1
elif s2_map[s2[r]] == s1_map[s2[r]] + 1:
# We were matched but now s2 count went above thus we are not matched.
matches -= 1
# now deal with incrementing l to keep window size same as length of s1,
# before we do, we remove current l from window and adjust counts
s2_map[s2[l]] -= 1
if s2_map[s2[l]] == s1_map[s2[l]]:
matches += 1
elif s2_map[s2[l]] + 1 == s1_map[s2[l]]:
# we were matched but removing char at l unmatched.
matches -= 1
# Now increment l
l+=1
# r will get incremented every loop.
# matches will be checked at the top
# final check if we matched with the removal of the last left char.
return matches == 26
- Minimum Window Substring
Solved
Hard
Topics
Companies Facebook 28
Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.
Example 2:
Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.
Example 3:
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.
Constraints:
m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
https://leetcode.com/problems/minimum-window-substring/description/
class Solution:
def minWindow(self, s: str, t: str) -> str:
charmap = defaultdict(int)
for c in t:
charmap[c] += 1
matches_needed = len(charmap.keys())
l = 0
minlen = len(s) + 1
subs = ""
for r in range(len(s)):
char = s[r]
if char in charmap:
charmap[char] -= 1
if charmap[char] == 0:
matches_needed = matches_needed - 1
while matches_needed == 0:
if r - l + 1 < minlen:
subs = s[l:r+1]
minlen = r - l + 1
lc = s[l]
if lc in charmap:
charmap[lc] += 1
if charmap[lc] > 0:
matches_needed += 1
l += 1
return subs
- Sliding Window Maximum
Hard
Topics
Companies Amazon
Hint
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
————— —–
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
https://leetcode.com/problems/sliding-window-maximum/description/
monotinic decreasing queue.
https://www.youtube.com/watch?v=DfljaUwZsOk&t=924s
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
l = 0
ret = []
for r in range(len(nums)):
while q and nums[q[-1]] < nums[r]:
q.pop()
q.append(r)
if r - l + 1 >= k:
ret.append(nums[q[0]])
l+=1
if q[0] < l:
q.popleft()
return ret
- Substring with Concatenation of All Words
don’t get bogged down on implementation, its not very straightforward
Attempted
Hard
Topics
Companies
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.
For example, if words = [“ab”,”cd”,”ef”], then “abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd”, and “efcdab” are all concatenated strings. “acdbef” is not a concatenated string because it is not the concatenation of any permutation of words.
Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example 1:
Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Output: [0,9]
Explanation:
The substring starting at 0 is “barfoo”. It is the concatenation of [“bar”,”foo”] which is a permutation of words.
The substring starting at 9 is “foobar”. It is the concatenation of [“foo”,”bar”] which is a permutation of words.
Example 2:
Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Output: []
Explanation:
There is no concatenated substring.
Example 3:
Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output: [6,9,12]
Explanation:
The substring starting at 6 is “foobarthe”. It is the concatenation of [“foo”,”bar”,”the”].
The substring starting at 9 is “barthefoo”. It is the concatenation of [“bar”,”the”,”foo”].
The substring starting at 12 is “thefoobar”. It is the concatenation of [“the”,”foo”,”bar”].
Constraints:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
s and words[i] consist of lowercase English letters.
https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150
Does not pass memory limits
~~~
from collections import defaultdict
class Solution:
def permutations(self, words):
perms = [[]]
for word in words:
curperm = []
for perm in perms:
for i in range(len(perm) + 1):
pc = perm.copy()
pc.insert(i, word)
curperm.append(pc)
perms = curperm
perms = list(map(lambda perm: ““.join(perm), perms))
return perms
def findSubstring(self, s, words):
Trie = lambda: defaultdict(Trie)
trie = Trie()
ret = []
# create trie of all permutations of the words
perms = self.permutations(words)
for perm in perms:
cur = trie
for c in perm:
cur = cur[c]
cur['#'] = True
wordlen = len(words[0]) * len(words)
for l in range(len(s) - wordlen + 1):
cur = trie
for j in range(l, l + wordlen):
if s[j] not in cur:
break
else:
cur = cur[s[j]]
if cur['#']:
ret.append(l)
return ret ~~~
from collections import defaultdict, Counter
class Solution:
def findSubstring(self, s, words):
word_count = Counter(words)
l = 0
output = []
wordlen = len(words[0])
winsize = wordlen * len(words)
def check(l):
needed = len(word_count.keys())
word_found = defaultdict(int)
for r in range(l, len(s), wordlen):
if r + wordlen > len(s):
break
w = s[r: r+wordlen]
if w in word_count:
word_found[w] += 1
while word_found[w] > word_count[w]:
ww = s[l:l+wordlen]
word_found[ww] -= 1
l += wordlen
if ww == w or word_found[ww] +1 == word_count[ww]:
needed += 1
if word_found[w] == word_count[w]:
needed -=1
else:
needed = len(word_count.keys())
word_found = defaultdict(int)
l=r+wordlen
if needed == 0:
output.append(l)
word_found[s[l:l+wordlen]] -= 1
needed+=1
l+=wordlen
for i in range(wordlen):
check(i)
return output
