Sliding window is essential for coding interviews, Window Sliding Technique is a computational technique that aims to reduce the use of nested loops and replace it with a single loop, thereby reducing the time complexity.
Given an array of integers and a number, write a function which finds the maximum sum of a subarray with the length of the number passed to the function. Ifex:
maxSubarraySum([]int{1, 1, 2, 4, 2, 3, 5, 1}, 4) //14
maxSubarraySum([]int{100, 200, 300, 400}, 2) //700
maxSubarraySum([]int{}, 2) //0
Here we will use the sliding window technique, the window will be of size n we will calculate the sum of the window elements and if it is bigger than maxSum, then it will be the new maxSum, notice that here we are not actually using the window, it is for representation purposes only
func maxSubarraySumWithPrint(list []int, n int) (maxSum int) {
maxSum = 0
tempSum := 0
window := []int{}
// go throuh the firs set if numbers
for i := 0; i < n; i++ {
window = append(window, list[i])
maxSum += list[i]
}
tempSum = maxSum
fmt.Print("Window representation: ", window, "; ")
fmt.Println("Sum is: ", tempSum)
for i := n; i < len(list); i++ {
window = window[1:]
window = append(window, list[i])
fmt.Print("Window representation: ", window, "; ")
tempSum = tempSum - list[i-n] + list[i]
fmt.Println("Sum is: ", tempSum)
maxSum = max(maxSum, tempSum) // this is just a regular max function
}
fmt.Println("Max sum is: ", maxSum)
return maxSum
}
Window representation: [1 1 2 4]; Sum is: 8
Window representation: [1 2 4 2]; Sum is: 9
Window representation: [2 4 2 3]; Sum is: 11
Window representation: [4 2 3 5]; Sum is: 14
Window representation: [2 3 5 1]; Sum is: 11
Max sum is: 14
Given a string s, find the length of the longest substring without repeating characters.
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.
Notice here that the windows is also just for representation, and in this example the window is not sliding
func LongestSubString(s string) int {
window := []byte{}
window_set := make(map[byte]int)
longest := 0
tempLongest := 0
for i := 0; i < len(s); i++ {
// if it is not in the set
char := s[i]
_, exists := window_set[char]
if exists {
// reset the window
window_set = make(map[byte]int)
window = []byte{}
window = append(window, char)
window_set[char] = 1
longest = maxUtil(tempLongest, longest)
tempLongest = 0
}
window = append(window, char)
window_set[char] = 1
tempLongest += 1
fmt.Println("Window representation: ", window)
}
longest = maxUtil(tempLongest, longest)
return longest
}
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
func IsAnagram(input map[byte]int, compare map[byte]int) bool {
return reflect.DeepEqual(input, compare)
}
func FindAllAnagrams(input string, match string) []int {
fmt.Println("FindAllDiagrams for ", input, " and ", match)
l := len(match)
anagrams := []int{}
// fill our match map
matchmap := make(map[byte]int)
for i := 0; i < l; i++ {
_, exists := matchmap[match[i]]
if exists {
matchmap[match[i]] += +1
} else {
matchmap[match[i]] = 1
}
}
// create string count of first window
byteCount := make(map[byte]int)
window := input[0:l]
for j := 0; j < len(window); j++ {
_, exists := byteCount[match[j]]
if exists {
byteCount[match[j]] += +1
} else {
byteCount[match[j]] = 1
}
}
// check if first window is an anagram
fmt.Print("Window representation: ", window, "; ")
if IsAnagram(byteCount, matchmap) {
anagrams = append(anagrams, 0)
fmt.Println("Is anagram")
}
// slide window into string input
for i := 1; i <= len(input)-l; i++ {
window = input[i : l+i]
fmt.Print("Window representation: ", window, "; ")
// delete left item outside window from byte count
leftByteOutsideWindow := input[i-1]
if byteCount[leftByteOutsideWindow] == 1 {
delete(byteCount, leftByteOutsideWindow)
} else {
byteCount[leftByteOutsideWindow] -= 1
}
// add rightest element in window to byte count
rightByteWindow := input[i+l-1]
if _, exists := byteCount[rightByteWindow]; exists {
byteCount[rightByteWindow] += 1
} else {
byteCount[rightByteWindow] = 1
}
// check if new window is an anagram
if IsAnagram(byteCount, matchmap) {
anagrams = append(anagrams, i)
fmt.Println("Is anagram")
} else {
fmt.Println()
}
}
return anagrams
}