# Array — Sliding Window

LeetCode(3) – Longest Substring Without Repeating Characters https://leetcode.com/problems/longest-substring-without-repeating-characters/

Wrong Code:

```class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""
Sliding Window: s[i, j] is the substring containing non-repeat characters.
Then, try to extend j, otherwise, extend i.
"""
char_pos = {}
i, j = 0, 0
res = 0
while i < len(s): # standard for loop of sliding window
if j + 1 < len(s) and s[j + 1] in char_pos:
i = char_pos[s[j + 1]] + 1 # problem is here. cannot jump on i.
del char_pos[s[j + 1]]
else:
j += 1
char_pos[s[j]] = j
res = max(res, j - i + 1)
return res
```

Code:

```class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""
Sliding Window: s[i, j] is the substring containing non-repeat characters.
Then, try to extend j, otherwise, extend i.
"""
freq = [0 for i in range(256)]
i, j = 0, -1
res = 0
while i < len(s): # standard for loop of sliding window
if j + 1 < len(s) and freq[ord(s[j+1])] == 0:
j += 1
freq[ord(s[j])] += 1
else:
freq[ord(s[i])] -= 1
i += 1
res = max(res, j - i + 1)
return res
```

LeetCode(438) Find All Anagrams in a String https://leetcode.com/problems/find-all-anagrams-in-a-string/

Code:

```class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
"""
anagram: the substring of s contains all characters in p and appear
the same number of times
"""
res = []
chars = {}
to_match = len(p)
for char in p:
chars[char] = chars[char] + 1 if char in chars else 1

i, j = 0, -1
while i < len(s) - len(p) + 1:
# if len(substring) is less than len(p), extend the substring
if j - i + 1< len(p):
j += 1
if s[j] in chars:
chars[s[j]] -= 1
# substract to_match only for non-redandunt character
to_match = to_match - 1 if chars[s[j]] >= 0 else to_match
else:
if to_match == 0:
res.append(i)
# pop s[i]
if s[i] in chars:
chars[s[i]] += 1
# increase to_match only for non_redandunt character
to_match = to_match + 1 if chars[s[i]] > 0 else to_match
i += 1

return res
```

This is what I saw in LeetCode, elegant codes. It does not declare much space but use hash to calculate and compare. Anagram: the hash of 2 strings should be the same.

```class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
LS, LP, S, P, A = len(s), len(p), 0, 0, []
if LP > LS: return []
for i in range(LP): S, P = S + hash(s[i]), P + hash(p[i])
if S == P: A.append(0)
for i in range(LP, LS):
S += hash(s[i]) - hash(s[i-LP])
if S == P: A.append(i-LP+1)
return A
```

another solution: use list to calculate how many times each character appears in substring of s and p. then compare two 26-elements list in each loop iteration. it is also constant time.

LeetCode 76. Minimum Window Substring https://leetcode.com/problems/minimum-window-substring/

Code:

```class Solution:
def minWindow(self, s: str, t: str) -> str:
res = ""
i, j = 0, -1
to_match = len(t)
chars = {}
for char in t:
chars[char] = chars[char] + 1 if char in chars else 1

while i < len(s):
if to_match > 0 and j < len(s) - 1:
j += 1
if s[j] in chars:
chars[s[j]] -= 1
to_match = to_match - 1 if chars[s[j]] >= 0 else to_match
elif to_match > 0 and j >= len(s) - 1:
break
else:
if res == "" or (j - i) < len(res):
res = s[i:j+1]
if s[i] in chars:
chars[s[i]] += 1
to_match = to_match + 1 if chars[s[i]] > 0 else to_match
i += 1
return res
```

LeetCode 209. Minimum Size Subarray Sum https://leetcode.com/problems/minimum-size-subarray-sum/

Code:

```class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
i, j = 0, -1
res = len(nums) + 1
sum = 0
while (i < len(nums)):
if j + 1 < len(nums) and sum < s:
j += 1
sum += nums[j]
else:
sum -= nums[i]
i += 1
if sum >= s:
res = min(res, j - i + 1)
return res if res != len(nums) + 1 else 0
```