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