Tech Interview Handbook Leetcode From Scratch 1 : Sliding Window
Tags: techinterviewhandbook, slidingwindows, leetcode
Published: 2023-11-11 15:46:14

Everything I write here is my summary of my learning and journey. My purpose of writing this article series is to make sure that I understand what I have learned, because they say that the capability of teaching others is the apex of understanding a topic. The other reasons are to train my English writing skills and to motivate myself.

I start learning Array first: https://www.techinterviewhandbook.org/algorithms/array/

I choose to use **Kotlin**.

For array, its **size** is **fixed**; **access** is **O(1)**, **search **is **O(n)**, **search **in **sorted **array is **O(log(n))**, **insert **is **O(n)**, **remove **is **O(n)**; **insert **at the **end **is **O(1)**; **remove **at the **end **is **O(1)**.

Given an array [1, 2, 3, 4, 5], [2, 3, 4] is called **subarray**; [1, 2, 3, 6] is not subarray but **subsequence**; and [2, 1, 3, 6] is not both

Check for **empty **array, **1-element** array, **2-element** array, **duplicate **values, **repeating **values; make sure of bounds when iterating.

Arrays and strings are **Sequences**.

Useful **technique **names: Sliding Window, Two Pointer, Right Traversing, Presort Array, Precomputation, Hash-tabling Array, Traversing More Than Once.

I plan to just jump into the solutions of the problem.

I start with this problem first to learn sliding window technique: **[Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)**.

After reading the problem’s description, I search on google with keyword “Sliding Window Technique Explained”, and ended up with this explanation: https://www.geeksforgeeks.org/window-sliding-technique/

From that, I can conclude that this technique really is just like its name, a window that is sliding from the start of an array to the end of it. The window has **two bounds**, namely windowStart and windowEnd, with **initial value** of 0. The window seems to **move **from **left to right**, with **windowEnd **keep **increasing **from 0 to **inputString.length**.

The **windowEnd increments** one at a time **regularly**, but **windowStart **only **increments **when the **goal **condition **fulfilled**. Not only that, **windowStart **increment **not regularly** (not only +1).

Go back to the Leetcode problem, I found this solutions and analyze it:

```
class Solution {
    fun lengthOfLongestSubstring(s: String): Int {

        val hashMap = HashMap<Char, Int>()
        var windowStart = 0
        var longest = 0

        for (windowEnd in s.indices) {

            val ch = s[windowEnd]

            if (hashMap.contains(ch)) {
                windowStart = max(windowStart, hashMap[ch]?.plus(1) ?: 0)
            }
            hashMap[ch] = windowEnd
            longest = max(longest, windowEnd - windowStart + 1)
        }

        return longest
    }
}
```
The naming of its variables make my head hurts, so I changed some.

```
class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        val inputString = s
        val inputStringLength = inputString.indices

        val alreadyReadCharMap = HashMap<Char, Int>()
        var windowStart = 0
        var longestWindowSize = 0

        for (windowEnd in inputStringLength) {
            val charAtWindowEnd = inputString[windowEnd]
            val hasDuplicateCharAtWindowEnd = alreadyReadCharMap.contains(charAtWindowEnd)

            if (hasDuplicateCharAtWindowEnd) {
                val windowStartBasedOnDuplicateChar = alreadyReadCharMap[charAtWindowEnd]?.plus(1) ?: 0
                windowStart = max(windowStart, windowStartBasedOnDuplicateChar)
            }

            alreadyReadCharMap[charAtWindowEnd] = windowEnd
            val currentWindowSize = windowEnd - windowStart + 1
            longestWindowSize = max(longestWindowSize, currentWindowSize)
        }

        return longestWindowSize
    }
}
```
I actually confused on why i need to use ?. on alreadyReadCharMap[charAtWindowEnd] when its existence already checked by if (hasDuplicateCharAtWindowEnd), but I’ll ignore it for now.

I find it easier to understand if I anchor my focus on for (windowEnd in inputStringLength) iteration, especially on charAtWindowEnd variable. It increments one by one from inputString start to the end, makes it easier to conseptualize.

I was also confused on the needs to do [1] windowStart = max(windowStart, windowStartBasedOnDuplicateChar) instead of just [2] windowStart = windowStartBasedOnDuplicateChar, but it actually needed for cases like inputString = “abcabcbb”.

Test case inputString = “abcabcbb”: The window will slide [a]bcabcbb -> [ab]cabcbb -> [abc]abcbb -> { [abca]bcbb -> abc[a]bcbb } -> { abc[ab]cbb -> here comes the problem on using [2] }

[2] will results in ab[cab]cbb instead of abc[ab]cbb, the windowStart is going backward. Actually, [2] pass three test cases “abcabcbb”, “bbbbb”, ”pwwkew” and accepted as valid Leetcode submission, but I don’t sure if its just a fluke or not. Nevertheless, I just prefer windowStart and windowEnd only going forward.