In the previous section, we showed what a sliding window is by doing a difficult problem with a sliding window using a double-endian queue. In this section, we will continue in-depth analysis and explore some modal solutions of sliding window problems.
01. Introduction to sliding Windows
For most sliding-window types, you’re looking at string matching. A more standard problem would give A pattern string B and A target string A. Then ask the question, find the substring in A that conforms to some limiting rules for B or the result of some limiting rules for A, and finally complete the combination or other requirements in the question idea.
For example, given a string s and a non-empty string p, find all substrings of the alphabetic alloword P in S and return the starting index of those substrings.
Or: give you a string S, a string T, please find in the string S: contains all the letters of T the smallest string.
Another example: Given a string s and some words of the same length. Find the starting position of the substring in S that happens to be formed by concatenating all the words in words.
These are all standard questions in this category. For this kind of problem, our common solution idea is to maintain a sliding window of variable length. Whether you use a double-pointer, a double-ended queue, or some other fancy cursor, the purpose is the same.
Now, let’s go through a problem
02. Topic analysis
| Problem 3: the oldest string without repeating characters |
|---|
| Given a string, find the length of the smallest string that does not contain repeating characters. |
Example 1:
Input: "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3Copy the codeExample 2:
Input: "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the codeExample 3:
Input: "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wke", its length is 3.Copy the code
Note that your answer must be the length of the substring, “pwke” is a subsequence, not a substring.
03. Solution analysis
To get straight to the problem, let’s say our input is “abcabcbb” and we just need to maintain a window to move through the input string. The diagram below:
When the next element does not appear in the window, we enlarge the window.
When the next element appears in the window, we zoom out and remove the element and the element to its left:
During the entire process, we can simply record the maximum value of the window. All we have to do is make the window as big as possible.
So what does our code do to maintain a window like this? Either queue, double pointer, or even map.
We demonstrate a double pointer:
public class Solution {
public static int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int result = 0, i = 0, j = 0;
while (i < n && j < n) {
//charAt: Returns the character at the specified position
if(! set.contains(s.charAt(j))) { set.add(s.charAt(j)); j++; result = Math.max(result, j - i); }else{ set.remove(s.charAt(i)); i++; }}returnresult; }}Copy the codeExecution Result:
We can tell by looking at it. In a worst-case scenario, we might access each character twice, left once, right once, in O(2N) time, which is unforgivable. If you don’t understand, look at the picture below:
Assuming our string is “abcdc”, we both access ABC twice.
So how do you optimize it further?
We can define the mapping of characters to indexes, rather than simply checking the existence of a character through a collection. This way, when we find a duplicate character, we can immediately skip the window without needing to revisit the previous element.
The optimized code is as follows:
public class Solution {
public static int lengthOfLongestSubstring(String s) {
int n = s.length(), result = 0;
Map<Character, Integer> map = new HashMap<>();
for (int right = 0, left = 0; right < n; right++) {
if (map.containsKey(s.charAt(right))) {
left = Math.max(map.get(s.charAt(right)), left);
}
result = Math.max(result, right - left + 1);
map.put(s.charAt(right), right + 1);
}
returnresult; }}Copy the codeExecution Result:
After the change, we found that although the time complexity has been improved, it is still slow! How to further optimize? We can use a 256-bit array instead of a HashMap for optimization. (Because there are 128 characters in the ASCII code table. ASCII code is one byte long, 8 bits, which can theoretically represent 256 characters, but many times only 128 characters are talked about. Specific reasons can go down to learn ~)
Further optimize the code:
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int result = 0;
int[] charIndex = new int[256];
for (int left = 0, right = 0; right < n; right++) {
char c = s.charAt(right);
left = Math.max(charIndex[c], left);
result = Math.max(result, right - left + 1);
charIndex[c] = right + 1;
}
returnresult; }}Copy the codeExecution Result:
We found a huge improvement in time complexity after optimization! Here is a brief explanation of the reason. When accessing an array or a HashMap, it is not always the case which is fast and which is slow. You need to think about the underlying implementation of the HashMap and the size of the data. But here, because the subscript of the data to be accessed is known, it can be directly addressed, so the query time is greatly shortened.
04,
So much for the question. Finally, it is generally recommended that if we want to analyze a problem, we should compress and compress again, and go to the end like cocooning and peeling silk, so as to complete the optimization of the problem as far as possible. It is not necessary to come up with the optimal solution, but never limit yourself to just completing the problem, that would be meaningless!
I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download
