Sliding Window

Aloha 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 ith day.

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: 5
Explanation: 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: 0
Explanation: 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 max SELL element after the BUY element. 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 = 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: 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.

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 = 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.

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 substring length and maxFreq of character. I want to try to subtract maxFreq from the substring length to get the other characters' count. 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 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!!!