Subarrays with K Different Integers

Problem:

Subarrays with K Different Integers

Given a positive integer array and a target k, return the number of subarrays with distinct integers equal to k. The subarray elements need to be contiguous but not necessarily distinct. 

For example, 

given [1,2,3,1,2] and k = 2

the output is 4.

there are 4 subarrays with 2 distinct integers.

[1, 2] [2, 3] [3, 1], [1, 2]

given [1,2,3,1,2] and k = 3

the output is 5.

there are 5 subarrays with 3 distinct integers.

[1, 2, 3], [1, 2, 3, 1] [2, 3, 1] [2, 3, 1, 2] [3, 1, 2]

given [1,2,3,1,2] and k = 0

the output is 5.

given [1,2,3,1,2] and k = 10

the output is 0. 

Solution:

This is a sliding window problem, quite similar to Longest Substring with At Most K Distinct Characters, here we are dealing with integer array instead of character array or string. 

We put the left pointer and right pointer of the sliding window at initial position 0. Then we move the right pointer to expand the sliding window and move the left pointer to shrink the sliding window. 

The right pointer is moved one step at a time, once the distinct integers in the sliding window is equal to k, we start to move the left pointer. Here we need to deal with the following situation:

1, 1, 1, 1, 1, 1, 2, 3, 4

All the subarrays with leading 1s are valid subarrays with distinct integers equal to 4. So we need 2 sliding windows that seak the begin and end of the 1s.

For the datastructure that count the distinct integers in a sliding window, we can use a HashMap to record the repeating time for each integer. 

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{1,2,3,1,2};
    int k = 2;
    System.out.println(subarrays(arr, k));
    k = 3;
    System.out.println(subarrays(arr, k));
    k = 1;
    System.out.println(subarrays(arr, k));
    k = 10;
    System.out.println(subarrays(arr, k));
  }
  public static int subarrays(int[] arr, int k) {
    if(k <= 1 || arr == null) throw new RuntimeException("invalid parameter");
    if(k == 1)
      return arr.length;
    int result = 0;
    SlidingWindow win1 = new SlidingWindow();
    SlidingWindow win2 = new SlidingWindow();
    int lp1 = 0;
    int lp2 = 0;
    for(int i = 0; i < arr.length; i++) {
      win1.add(arr[i]);
      win2.add(arr[i]);
      while(win1.getNumOfUnique() > k) {
        win1.remove(arr[lp1++]);
      }
      while(win2.getNumOfUnique() >= k) {
        win2.remove(arr[lp2++]);
      }
      result += lp2 - lp1;
    }
    return result;
  }
 
  private static class SlidingWindow {
    private int numOfUnique = 0;
    private Map<Integer, Integer> freq = new HashMap<>();
    public void add(int i) {
      freq.put(i, freq.getOrDefault(i, 1));
      if(freq.get(i) == 1) {
        numOfUnique++;
      }
    }
    public void remove(int i) {
      int count = freq.get(i);
      if(count == 1) {
        numOfUnique--;
        freq.remove(i);
      }
    }
    public int getNumOfUnique() {
      return numOfUnique;
    }
  }
}

The time complexity is O(N), the left pointers and right pointer only iterate the integer array once. 

The space complexity is O(N), the HashMap could have size N.

Longest Repeating Character Replacement

Problem:

Given a string s that consists of only uppercase English letters, you can perform at most k operations on that string.

In one operation, you can choose any character of the string and change it to any other uppercase English character.

Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

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:

We can use a sliding window, the right edge increase 1 at each step. At each step, we get the sliding window size r - l + 1, we also update the character frequency freq[c] and find the character with the highest frequency maxLen, for all the characters in the sliding window. If r -l + 1 - maxLen <= k, we are able to change all the other characters in the sliding window to the highest frequency character. As a result, we update the result for the current window size, then go to the next step. 

If r -l + 1 - maxLen > k, we should stop expanding, and shrink the sliding window to restore the constraint r -l + 1 - maxLen <= k. We move the left edge one step at a time. At each step, we get the sliding window size r - l + 1, we also update the character frequency freq[c] and find the character with the highest frequency maxLen, for all the characters in the sliding window. 

import java.util.stream.*;
class Solution {
  public static void main(String...args) {
    System.out.println(longestSub("ABAB", 2));
    System.out.println(longestSub("ABAB", 3));
    System.out.println(longestSub("ABAB", 1));
    System.out.println(longestSub("ABAB", 10));
  }
  //AABABBA 1 ---- A 1, B 2
  //    .
  //      .
  public static int longestSub(String str, int k) {//
    int l = 0; //sliding window left pointer
    int maxLen = 0; //max repeating character in the window
    int[] freq = new int['Z' - 'A' + 1];
    int result = 0;
    for(int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      freq[c - 'A']++;
      maxLen = Math.max(maxLen, freq[c - 'A']);
      if(i - l + 1 - maxLen <= k) {
        result = Math.max(result, i - l + 1);
      }
     
      while(i - l + 1 - maxLen > k) {
        freq[str.charAt(l++) - 'A']--;
        maxLen = IntStream.of(freq).max().getAsInt();
      }
    }
    return result;
  }
}

The time complexity is O(N), the left edge and right edge iterate the string length at most once. When we move the left edge, for each step, we need to find the maxLen with  maxLen = IntStream.of(freq).max().getAsInt(); the cost is 26 comparisons at most.

The space complexity is O(1), the character frequency counting array has size 26.

Longest Substring with At Most K Distinct Characters

Problem:

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For Example:

Given string "hmhkl" and k = 2

Output: 3

T is "hmh" with length 3, which contains 2 distinct characters.

Solution:

We can solve this problem with sliding window. The left and right pointer initially point to first character. Move the right pointer expands the sliding window and adds new character; while move the left pointer shrink the sliding window and remove old character. We just have to count how many distinct characters are in the sliding window. To achieve that goal, we can use an integer to count the distinct characters and a map to count the repeating times for each character. The map is updated when we add or remove a character, the count is updated when we meet a new character or the map's count for a character decreases to 0. Actually, assuming the string only contains lowercase characters, we can use a size 26 int array to replace the map for the same purpose.

Once we have the count of distinct characters in the sliding window, we can decide when to expand the sliding window and when to shrink the sliding window. When the count is k+1, we need to register a max length then we need to shrink the sliding window until the count is k again.

class Solution {
  public static void main(String...args) {
    System.out.println(longestSub("hmhkl", 2));
    System.out.println(longestSub("klhmhkl", 2));
    System.out.println(longestSub("klhmh", 2));
    System.out.println(longestSub("klhmhklklhmhkl", 2));
    System.out.println(longestSub("bbbbb", 1));
    System.out.println(longestSub("babab", 1));
  }

  public static int longestSub(String str, int k) {
    if(str == null || str.length() == 0)
      return 0;
    int count = 0;
    int[] counter = new int['z' - 'a' + 1]; //26
    int maxLen = 0;
    int tmpMax = 0;
    int l = 0;
    for(int i = 0; i < str.length(); i++) {  //babab
      char c = str.charAt(i); //a
      counter[c - 'a']++;   //b 0, a 1
      tmpMax++;   //2
      if(counter[c - 'a'] == 1) {
        count++;  //2
        if(count > k) {
          maxLen = Math.max(maxLen, tmpMax - 1);  //1
          while(l < i) {
            c = str.charAt(l++); //b
            counter[c - 'a']--;
            tmpMax--;
            if(counter[c - 'a'] == 0) {
              count--;
              break;
            }
          }
        }
      }
    }
    maxLen = Math.max(maxLen, tmpMax);
    return maxLen;
  }
}

The time complexity is O(N), the left and right pointer go through the string only once at most.

The space complexity is O(1), we only has a size 26 array and a few variables for this algorithm.

Moving Stones Until Consecutive II

Problem:

On an infinite number line, the position of the i-th stone is given by stones[i].  Call a stone an endpoint stone if it has the smallest or largest position.

Each turn, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.

In particular, if the stones are at say, stones = [1,2,5], you cannot move the endpoint stone at position 5, since moving it to any position (such as 0, or 3) will still keep that stone as an endpoint stone.

The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.

When the game ends, what is the minimum and maximum number of moves that you could have made?  Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

Example 1:

Input: [7,4,9]
Output: [1,2]
Explanation:
We can move 4 -> 8 for one move to finish the game.
Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game.
Example 2:

Input: [6,5,4,3,10]
Output: [2,3]
We can move 3 -> 8 then 10 -> 7 to finish the game.
Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game.
Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move.
Example 3:

Input: [100,101,104,102,103]
Output: [0,0]

Solution:

Let's play the game for a while.

First of all, we should put the stones in the right positions, otherwise this game won't be a playable fun game.

For maximum it is just the sum of the gaps between each stone. We can move the left boundary stone next to the right boundary stone, then move right boundary stone next to the left boundary stone, so on and so forth. Each move shrinks the total length by one. But if we take the 1st stone then we cannot count the gaps between 1st and 2nd stone. Similarly if we take the last stone then we cannot count the gaps between last and 2nd last stone. Thus we need to take the maximum of these two cases.

Next let's work on the minimum number of moves. For the first move, let's pick up the stone from the side that will eliminate more empty spaces after moving, a reasonable choice. Where should the stone be put down? There are many choices which all makes sense, but those positions should be somewhere in the range with most dense stone populations. That tuition leads us to a mathematical imagination for how the end game should look like.

For minimum number of moves, the final arrangement will be of the form [a, a+1, a+2, ... a+L-1] for L stones for some 'a'. The possible values of 'a' are all the stone positions in the given input array. The reason a is at stone position is because, if it is not at stone position, we can move the range to [a+1, a+2, ... a+L], which didn't lost a stone at left boundary, but could possibly included a new stone at the right boundary. More stone in the range is a favorable situation. We can keep doing this until a is at the next stone position. The right boundary a+L-1 could be at either stone position or empty position.

For each possible 'a', check how many positions (from a to a+L-1) already have stones. We need to fill in the missing remaining positions. Thus if there are K missing positions we need K moves to fill them. Compute K for each value of 'a' and take their minimum.

To achieve the goal, we can use sliding window. The window initially contains 2 stones. The stones in the window exclude the right boundary. We expand the window one stone interval if the positions inside the window can not hold L stones, otherwise register a min move count, then shrink the window one stone interval.
When register a min move count, there are 2 conditions:

1. There is only one empty position in the sliding window. In that case, we have to move the right boundary stone to complete the game. We don't move the left boundary stone to complete the game, because in the next iteration, when we shrink the sliding window, that case will be covered. When we move the right boundary stone to finish the game, we need to make sure the empty position is not next to the right boundary.
2. There are more than one empty positions in the sliding window. In that case, we know there are at least 2 stones outside the sliding window. We can use 1 stone to fill the empty position next to the right boundary of the sliding window, so that we won't get into condition 1 in later moves.  

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[] pos = new int[]{7,4,9};
    int[] ans = maxmin(pos);
    System.out.println("[" + ans[0] + ", " + ans[1] + "]");
  }

  public static int[] maxmin(int[] pos) {
    if(pos.length == 2) {
      throw new RuntimeException("more than 3 stones please");
    }
    int[] ans = new int[2];
    Arrays.sort(pos);
    ans[0] = min(pos);
    ans[1] = max(pos);
    return ans;
  }

  //4  .  .  7  .  9
  private static int min(int[] pos) {
    int l = 0;   //sliding window left boundary
    int r = 1;  //sliding window right boundary
    int min = Integer.MAX_VALUE;
    int stones = 1;
    int gaps = 0;
    while(r < pos.length) {
      if(pos[r] <= pos[l] + pos.length-1) { //expand sliding window
        stones++;
        r++;
      } else {
        gaps = pos.length - stones;
        if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
          min = Math.min(min, gaps);
        }
        l++; //shrink sliding window
        stones--;
      }
    }
    gaps = pos.length - stones;
    if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
      min = Math.min(min, gaps);
    }
    return min;
  }

  //4  .  .  7  .  9
  private static int max(int[] pos) {
    int total = pos[pos.length - 1] - pos[0] + 1;  //9 - 4 + 1 = 6
    int space = total - pos.length;
    //remove 1st interval or last interval
    return Math.max(space - (pos[1] - pos[0] - 1), space - (pos[pos.length - 1] - pos[pos.length - 2] - 1));
  }
}

The time complexity for sorting is O(NlogN), the space complexity is O(1).

Number of Submatrices That Sum to Target

Problem:

Given a matrix, and a target, return the number of non-empty submatrices that sum to target.

For example, given matrix
{
{0, 1},
{0, 1}
}
and target 0, the output should be 3.
Given the same matrix and target 1, the output should be 4.
Given the same matrix and target 2, the output should be 2.
Given the same matrix and target 3, the output should be 0.

Solution:
We have solved Subarray Sum Equals K before, this problem can be converted to that problem then get solved. The matrix involved in Subarray Sum Equals K is a 1D array, while we are dealing with 2D array here.

We can calculate the prefix sum of the original array, then any submatrices' sum can be calculated with from the prefix sum matrix. curr_sum = sum[r2][col] - sum[r1 - 1][col]. In 2D the prefix sum is a sum of the current value with the integers above or on the left.

prefix sum

For example:

              0 0 0
0 1         0 0 1
0 1         0 0 2


Now we can write the code

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[][] arr = new int[][]
                            {
                            {0, 1},
                            {0, 1}
                            };
    int target = 0;
    System.out.println(numOfsubArrays(arr, target));
    target = 1;
    System.out.println(numOfsubArrays(arr, target));
    target = 2;
    System.out.println(numOfsubArrays(arr, target));
    target = 3;
    System.out.println(numOfsubArrays(arr, target));
  }
 
  public static int numOfsubArrays(int[][] arr, int target) {//0
    int r = arr.length;   //2
    int c = arr[0].length;  //2
    int[][] sum = new int[r+1][c+1]; //sum matrix is bigger than the orginal max
    //fill the sum from index 1,1 to r,c, not filled cells remain 0.
    for(int i = 1; i < r+1; i++) {
      for(int j = 1; j < c+1; j++) {
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i-1][j-1];
      }
    }
    /*
    0 0 0
    0 0 1
    0 0 2
    */
    int count = 0;
    Map<Integer, Integer> vals = new HashMap<>();
    for(int i = 0; i < r; i++) {
      for(int j = i+1; j < r+1; j++) {
        //with fixed row, 2D Subarray Sum Equals K problem converts to 1D Subarray Sum Equals K
        vals.clear();
        for(int k = 0; k < c+1; k++) {  //k=0, so we can have val.put(0, 0)
          int delta = sum[j][k] - sum[i][k];
          count += vals.getOrDefault(delta - target, 0);
          vals.put(delta, vals.getOrDefault(delta, 0) + 1);
        }
      }
    }
    return count;
  }
}

The time complexity is O(RRC) for the 3 layered loop, the space complexity is O(RC) for the prefix sum matrix.

see also:
Subarray Sum Equals K

Sliding Window Maximum

Problem:

Given an integer array and an Integer k, k represents a sliding window with size k that starts at the array's left end, moves one step at a time until reaches the array's right end. Each time the sliding window moves, it brings in a new number from right and removes an old number at left. Return an array which contains the max number in the sliding window at each move.

For Example:

Given array [1,3,-1,-3,5,3,6,7], and k = 3
The output is: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

 1 <= k <= array.length

Solution:

The brutal force solution is search k elements for the max at each array index from 0 to n - k. The time complexity will be nk.

There is a time complexity O(N) solution if we redesign the problem.

We can divide the original array into k sized chunks. When the k sized sliding window slides through the array, the chunk's boundary will cut the window into 2 parts. The original problem of finding the max value in the sliding window is converted to find the max value for the left half, max value for the right half, then combine the 2 max values we can find the max value in the sliding window.

imaginary boundary cut the k sized sliding window into 2 halves

With the imaginary k sized boundary added, the rest of the work is easy. In order to find the max value for the left half of the sliding window, we only have to scan from the boundary leftward, for the max value for the right half of the sliding window, we only have to scan from the boundary rightward. We can scan these max values and store them in array left and right. Then we can iterate the original array, use the pre-scanned left and right max value arrays to find the left half and right half's max values. 

import java.util.*;
public class Solution {
  public static int[] maxNum(int[] arr, int k) {
    int n = arr.length;
    int[] result = new int[n - k + 1];
    int[] left = new int[n];
    int[] right = new int[n];
    left[0] = arr[0];
    right[n - 1] = arr[n - 1];
    for(int i = 1; i < n; i++) {
      //left -> right
      if(i % k == 0) {
        left[i] = arr[i];  //reset max at boundary
      } else {
        left[i] = Math.max(left[i - 1], arr[i]);  //compare with left
      }
      //right -> left
      if((n - i) % k == 0) {
        right[n - i - 1] = arr[n - i - 1];  //reset max at boundary
      } else {
        right[n - i - 1] = Math.max(right[n - i], arr[n - i - 1]); //compare with right
      }
    }
    for(int i = 0; i <= n - k; i++) {
      result[i] = Math.max(right[i], left[i + k - 1]);  //right[i] is the max value of the sliding window's left half
    }
    return result;
  }
 
  public static void main(String...args) {
    int[] arr = new int[]{1,3,-1,-3,5,3,6,7};
    for(int i : maxNum(arr, 3)) {
      System.out.print(i + " ");
    }
  }
}

We need to iterate the array once to generate the max value array left and right, we need to iterate the array the second time to calculate the sliding window's left and half max value, then combine them to find the max value in the sliding window. The time complexity is O(N), the space complexity is O(N) because of the left and right array for max values.

Minimum Window Substring II

Problem:

Given a Source string and a Target string, find the shortest substring in Source string that contains all unique characters in target string.

For Example:

Given source string "YMNZZDXQFHYAZX" and target string "XYZ"

The shortest substring in "YMNZZDXQFHYAZX" that contains "XYZ" is "YAZX"
Note:

If no solution, return the empty string "".
We can assume there is only one unique answer window in source string.

Solution:

The problem is fit for sliding window. We use two pointers to mark a focus window's left and right edge. We slide the right pointer to add more characters to the window for consideration, we move the left pointer to remove characters from the window. For a particular window, we exam the condition to update a result candidate. The remaining design work is now boiling down to when to move right pointer, when to move left pointer. 

For this particular problem, we move the right pointer 1 step at a time until the condition "substring in Source string that contains all unique characters in target string" meets. Once the condition is met, we move the left pointer one step at time, until the condition no longer meet, during the process, we can find the shortest substring end at the right pointer's position that satisfy the condition. 

After that, we move the right pointer in order to restore the condition, then we move the left pointer in order to break the condition, during the process, we will find another shortest substring candidate. 

Then we repeat until the right pointer reach the end of the string.

import java.util.*;
public class Solution {
  public static String shortestSubstring(String s, String t) { //YMNZZDXQFHYAZX XYZ
    if(s.length() == 0 || t.length() == 0) return "";
    HashMap<Character, Integer> counter = new HashMap<>();
    int left = 0, right = 0;
    int minL = 0, minR = Integer.MAX_VALUE;  //10,13
    Set<Character> tt = new HashSet<>();
    for(Character c : t.toCharArray()) {
      tt.add(c);
    }
    while(right < s.length()) {
      char c = s.charAt(right);
     
      if(tt.contains(c)) {
        counter.put(c, counter.getOrDefault(c, 0) + 1);
      }
     
      while(counter.size() == tt.size()) {
        if(right - left < minR - minL) {
          minL = left;
          minR = right;
        }
        char tmp = s.charAt(left);
        if(tt.contains(tmp)) {
          if(counter.get(tmp).equals(1)) {
            counter.remove(tmp);
          } else {
            counter.put(tmp, counter.get(tmp) - 1);
          }
        }
        left++;
      }
      right++;
    }
    if(minR == Integer.MAX_VALUE)
      return "";
    return s.substring(minL, minR+1);
  }
  public static void main(String...args) {
    System.out.println(shortestSubstring("YMNZZDXQFHYAZX", "XYZ"));
  }
}

The time complexity is O(S + T), we iterate Source and Target at least once. The space complexity is O(S + T), the HashSet has size O(T) and the HashMap has size O(T) but the final string could have size O(S). 

Longest Substring Without Repeating Characters

Problem:

Given a string, find the length of the longest substring without repeating characters.

For Example:

Input: "xxyzxzzy"
Output: 3
Explanation: The answer is "xyz", with the length of 3.


Input: "mmmmmm"
Output: 1
Explanation: The answer is "m", with the length of 1.
Example 3:

Input: "hmmqmym"
Output: 3
Explanation: The answer is "qmy", with the length of 3.

Solution:

We can use a sliding window, find all the combinations of the end index and start index, check if substring(start, end) have duplicate character, the start and end index need two loops, check duplicate need another loop. The total cost will be O(N^3).

We can do this smarter.
The duplicate check can be done with a HashMap, which has cost of 1 instead of N.

If substring [start, end) has already been checked for duplicate, then to check duplicate for substring [start, end + 1) is to check if the character at index end is already in the substring [start, end), which is a cost 1 HashMap call.

Anther observation is: if a character has duplicate at index k in the range [i, j), the start index can advance to k + 1, skip all the duplicate check between [i, k]. The reason is, any substring start before k, will bound to find duplicate at current examine index, the only chance for no duplicate substring start at k + 1.

import java.util.*;
class FindLongestSubString {

  //abbcprqmpaq
  private static String getLongest(String word) {
    //sliding window, advance start index and end index
    Map<Character, Integer> nextPos = new HashMap<>();
    int maxLength = 0;
    int startIndex = 0;
    for(int start = 0, end = 0; end < word.length(); end++) {  //end = 10q
      if(nextPos.containsKey(word.charAt(end))) {
        start = Math.max(start, nextPos.get(word.charAt(end)));  //7
      }
      if(end - start + 1 > maxLength) {    //6
          maxLength = end - start + 1;    //6
          startIndex = start;  //2
      }
      nextPos.put(word.charAt(end), end + 1);  //a10;b3;c4;p9;r6;q11;m8
    }
    return word.substring(startIndex, startIndex + maxLength);
  }
  public static void main(String...args) {
    String result = getLongest("abbcprqmpaq");
    System.out.println(result);
    result = getLongest("abbcprqmpaqx");
    System.out.println(result);
    result = getLongest("abbcrqmppaqx");
    System.out.println(result);
    result = getLongest("abbcprqmpazx");
    System.out.println(result);
    result = getLongest("mznhieabbcprqmpazx");
    System.out.println(result);
  }
}

The time complexity is O(N), we need to iterate the word, cost for hashmap is 1. The space complexity is O(N) which is the size of the hashMap

This is a typical sliding window problem, we use a mask to hide the whole string, only reveal a window for part of the string, then study its property. The sliding window has a left and right edge, we move the left edge to mask unconcerned characters, we move the right edge to reveal more character into concern. For this particular problem, we move the right edge 1 step at a time to reveal one more character until visited the whole string. If the new character has been seen before at index k, we can safely move left edge to k+1, ignoring all the substrings before position k. It is because any substring that includes the same character at index k will have duplicate. Now the substring in the sliding window's left and right edge form a candidate for the longest substring without duplicate. To remember the last time we saw a character, we can use a HashMap, however, since the characters are limited, we can use an array for the same purpose, size 128 array for ASCII and 256 for extended ASCII.

public class Solution {
  public static String longestSubString(String str) { //x
    String longest = "";
    int[] lastSeen = new int[256];
    int i = 0, j = 0;
    while(j < str.length()) { //i=2, j=5
      Character c = str.charAt(j++);  //x
      i = Math.max(i, lastSeen[c]);
      lastSeen[c] = j;  //x:5, y:3, z= 4
      if(longest.length() < j - i) {
        longest = str.substring(i, j);  //xyz
      }
    }
    return longest;
  }
  public static void main(String...args) {
    System.out.println(longestSubString("xxyzxzzy"));
  }
}

The time complexity is O(N), we only go through the array once. The space complexity is O(N), the longest substring can only be as long as N.