The Algorithm of Using a Sliding Window.

A sliding window is an abstract concept commonly used in array/string problems. It is effective to solve problems like finding the Longest subarray/substring following a certain pattern. It uses 2 indices i and j to keep track of start and end of the window respectively.

Array sequence: 1,2,3,4,5,6,7. 
a window of [3,4,5,6] can be indicated by
i-> 2;
j-> 5;

Here is an example of using this concept:

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring"pwke" is a subsequence and not a substring.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<Character>();
        int i = 0; int j = 0;
        int max_len = 0;
 
        while (i < s.length() && j < s.length()){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j));
                j++;
                max_len = max_len>(j-i)? max_len : (j-i);
           }else{
                set.remove(s.charAt(i));
                i++;
                }
           }
 
         return max_len;
     }
}

 

 

Advertisements