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