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;
     }
}

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s