# Sliding Window

### In this article, explore solutions to popular interview problems using a sliding window.

Join the DZone community and get the full member experience.

Join For FreeAloha guys. We are going on about popular interview questions. Today we will solve a few problems with the sliding window approach.

## Best Time To Buy and Sell Stock

Our first problem is taken from "LeetCode Algorithm Challenges: Best Time to Buy and Sell Stock."

**Description **

You are given an array `prices`

where `prices[i]`

is the price of a given stock on the `i`

day.^{th}

You want to maximize your profit by choosing a **single day** to buy one stock and choosing a **different day in the future** to sell that stock.

Return *the maximum profit you can achieve from this transaction*. If you cannot achieve any profit, return `0`

.

**Example 1:**

Input:prices = [7,1,5,3,6,4]Output:5Explanation:Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

**Example 2:**

Input:prices = [7,6,4,3,1]Output:0Explanation:In this case, no transactions are done and the max profit = 0.

### Solution

First of all, as usual, we should understand what we will do. It looks like we should ** find a min BUY** element and

**. We can try to get each element in the array in the first loop and then compare all other elements in the second loop, like**

*max SELL element after the BUY element*`max = Math.max(max, prices[j] - prices[i]);`

. Let's try to change the second loop, and instead of having two loops, we can use `while`

.

We can use "window" with start and end pointers. Then if our `arr[end]`

is bigger than `arr[start]`

, we can increase the end pointer, right? And in our "window," we will have all elements bigger than `arr[start]`

. I hope that is clear: we increase the end pointer if and only if `arr[end]`

is bigger than `arr[start]`

. All elements after the start pointer are bigger.

That is why, if suddenly we have `arr[end] < arr[start]`

, we can move the start pointer to the end pointer position and increase the end pointer again. Wow, it can be really tricky to understand, but I hope you got it. Let's deep dive and check the code for it.

### Code

```
public int maxProfit(int[] prices) {
int rez = 0;
int start = 0;
int end = start + 1;
while (end < prices.length){
if (prices[end] > prices[start]){
rez = Math.max(rez, prices[end] - prices[start]);
end++;
} else {
start = end;
end++;
}
}
return rez;
}
```

And the second mind-blowing variant:

```
public int maxProfit2(int[] prices) {
int max = 0;
for(int i = 0; i < prices.length; i ++){
for(int j = i+1; j < prices.length; j ++){
max = Math.max(max, prices[j] - prices[i]);
}
}
return max;
}
```

## Longest Substring Without Repeating Characters

Our next problem is taken from "Length of the longest substring without repeating characters."

**Description**

Given a string `s`

, find the length of the **longest** **substring **without repeating characters.

**Example 1:**

Input:s = "abcabcbb"Output:3Explanation:The answer is "abc", with the length of 3.

**Example 2:**

Input:s = "bbbbb"Output:1Explanation:The answer is "b", with the length of 1.

**Example 3:**

Input:s = "pwwkew"Output:3Explanation: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.

### Solution

Alright, we want to find the longest substring without repetitions. To check repetitions we can use `Set`

, for example. We also need to check the length of the substring, which is a central problem in this task. To do it, let's prepare two pointers: start and end. Then we can move the *end-pointer* to the next position only if the char on the *end-pointer is unique*. What does that mean? It means that we would check the Set, and if the Set doesn't contain a character, we will add it and move the end-pointer.

But we still don't have length. And what should we do with repetitions? Now we need to move the start-pointer while our end-pointer doesn't persist in the `Set`

: then, check the length between the start and end pointers*.*

The first code variant should be more clear for you, but the second one is more optimal. Enjoy:

### Code

```
public int lengthOfLongestSubstring(String s) {
Set<Character> dict = new HashSet<>();
int rez = 0;
int left = 0;
for(int right = 0; right < s.length(); right++){
while(dict.contains(s.charAt(right))){
dict.remove(s.charAt(left));
left++;
}
dict.add(s.charAt(right));
rez = Math.max(rez, right - left + 1);
}
return rez;
}
```

Second variant:

```
public int lengthOfLongestSubstring2(String s) {
int[] dict = new int[128];
int max = 0;
int curMax = 0;
int start = 0;
int skip = 0;
while(start < s.length()){
int idx = s.charAt(start) - ' ';
if (dict[idx] == 0){
dict[idx] = 1;
start++;
curMax++;
} else {
max = Math.max(max, curMax);
int skipIdx = s.charAt(skip) - ' ';
dict[skipIdx] = 0;
skip++;
curMax--;
}
}
return Math.max(max, curMax);
}
```

## Longest Repeating Character Replacement

The last problem for today comes from "LeetCode: Longest Repeating Character Replacement."

**Description**

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 = 2Output:4Explanation:Replace the two 'A's with two 'B's or vice versa.

**Example 2:**

Input:s = "AABABBA", k = 1Output:4Explanation:Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.

### Solution

That is a mind-blowing problem for me. I strongly recommend you guys debug it and try to understand each iteration in the code above.

The main idea of this algorithm is to find the maximum repeating value in the word on each step (`maxFreq`

). Then we can calculate the ** substring length** as

`end - start + 1`

. It will be the length of our current substring. Now we have the **and**

*substring length***of character. I want to try to subtract**

*maxFreq***from the**

*maxFreq***to get the**

*substring length***I want to repeat it because it is a crucial moment in this problem. I want to calculate the substring length and substruct the number of the most frequent character. It gives me**

*other characters' count.***.**

*the number of other characters*After that, we need to compare it with `k`

. If the count of unique characters is bigger than `k`

, we need to move the `start-pointer`

, and we would do it till the unique char count is bigger than `k`

.

Do you have a more optimal solution? Could you please share it with me?

### Code

```
public int characterReplacement(String s, int k) {
int start = 0;
Map<Character, Integer> map = new HashMap<>();
int max = 0;
int maxFreq = 0;
for (int end = 0; end < s.length(); end++) {
char cur = s.charAt(end);
map.put(cur, map.getOrDefault(cur, 0) + 1);
maxFreq = Math.max(maxFreq, maxCharLength(map));
while ((end - start + 1) - maxFreq > k) {
char startChar = s.charAt(start);
map.put(startChar, map.get(startChar) - 1);
start++;
}
max = Math.max(max, end - start + 1);
}
return max;
}
private int maxCharLength(Map<Character, Integer> map) {
int max = 0;
for (Integer i : map.values()){
max = Math.max(max, i);
}
return max;
}
```

Don't worry if you don't understand it on the first try. For me, "sliding window" is one of the most challenging problems at all. Good luck!!!

Opinions expressed by DZone contributors are their own.

Comments