Let us go through some of the common problems related to sliding window.
Rabin Karp is used for finding a substring of a string. This uses a form of sliding window. Here the pattern is read from left to right. So, if we have pattern length is 3 and string is “23456”, then the hashes would be "234", "345", and "456".
Here are the steps:
Here is the code in Java.
static void search(String pat, String txt, int Q) {
int M = pat.length(), N = txt.length(), j, pow = 1, d = 256;
int pHash= 0, /* hash for pattern */ tHash = 0; /* hash for text */
// Preprocessing: The value of pow would be "pow(d, M-1) % Q"
for (int i = 0; i < M-1; i++) pow = (pow*d) % Q;
// Preprocessing: Calculate the hash value of pattern.
for (int i = 0; i < M; i++) {
pHash = (d*pHash + pat.charAt(i)) % Q;
}
// Sliding window steps: DAL
for (int i = 0; i < N; i++) {
// Step1 (Delete): Calculate hash value for next window of text: Remove leading digit
if (i >= M) {
tHash = (tHash - txt.charAt(i-M)*pow) % Q;
// We might get negative value of t, converting it to positive
if (tHash < 0) tHash = (tHash + Q);
}
// Step2 (Add): Add the current value.
tHash = (d * tHash + txt.charAt(i)) % Q;
// Step3 (Process): Check the hash values of current window of text and pattern.
// If the hash values match then only check for characters on by one
if (i >= (M-1)) {
if (tHash == pHash) {
if (pat.equals(txt.substring(i-M+1, i+1)))
System.out.println("Pattern found at index " + (i-M+1));
}
}
}
}
/* Driver program to test above function */
public static void main(String[] args) {
String txt = "GEEKS FOR GEEKS";
String pat = "GEEK";
int q = 101; // A prime number
search(pat, txt, 1 << 20 -1);
}
The average and best case running time of the Rabin-Karp algorithm is O(n+m), but its worst-case time is O(nm). Worst case of Rabin-Karp algorithm occurs when all characters of pattern and text are same as the hash values of all the substrings of txt[] match with hash value of pat[]. For example pat[] = “AAA” and txt[] = “AAAAAAA”.
Problem: https://leetcode.com/problems/minimum-window-substring/
Given two strings s and t of lengths m and n respectively, we need to return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
Here is the code:
public String minWindow(String s, String t) {
int min = Integer.MAX_VALUE, count = 0, lenTarget = t.length(), i = 0;
String best = "";
int[] dp = new int[256];
for (char c: t.toCharArray()) dp[c]++;
for (int j = 0; j < s.length(); j++) {
char c = s.charAt(j);
if (dp[c]-- > 0) count++;
while (count >= lenTarget && i <= j) {
if (count == lenTarget) {
if (min > (j-i+1)) {
min = Math.min(min, j-i+1);
best = s.substring(i, j+1);
}
}
c = s.charAt(i);
if (++dp[c] > 0) count--;
i++;
}
}
return best;
}
Problem: https://leetcode.com/problems/permutation-in-string/
Given two strings s1 and s2, return true if s2 contains the permutation of s1. The insight is to use Minimum Window Substring (MWS). The solution is similar to that of an anagram.
Example 1: Input: s1 = "ab" s2 = "eidbaooo"/Output: True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2: Input:s1= "ab" s2 = "eidboaoo"/Output: Falsek
Here is the code (in Java):
public boolean checkInclusion(String s1, String s2) {
int[] dp = new int[26];
int[] dp0 = new int[26];
for (char c: s1.toCharArray()) dp0[c-'a']++;
int k = s1.length(), count = 0, i = 0;
for (int j = 0; j < s2.length(); j++) {
char c = s2.charAt(j);
dp[c-'a']++;
if ((dp0[c-'a'] > 0) && (dp[c-'a'] <= dp0[c-'a'])) count++;
if (j >= k) {
c = s2.charAt(j-k);
dp[c-'a']--;
if (dp[c-'a'] < dp0[c-'a']) count--;
}
if (count == k) {
return true;
}
}
return false;
}
Problem: https://leetcode.com/problems/find-all-anagrams-in-a-string/
In this problem, we are given a string s and a pattern p and we need to find all occurrences in s such that an anagram of p starts there.
Example1: Input: s: "cbaebabacd" p: "abc"/Output: [0, 6] Example2: Input: s: "abab" p: "ab"/Output: [0, 1, 2]
We can use minimum-window-substring template. It is quite similar to the earlier "Permutation in String" problem. This is actually a fixed window problem since the window that we are exploring has a fixed size.
public List<Integer> findAnagrams(String s, String p) {
int[] dp = new int[26];
int[] dp0 = new int[26];
List<Integer> ret = new ArrayList<>();
int k = p.length(), count = 0;
for (int i = 0; i < p.length(); i++) dp0[p.charAt(i)-'a']++;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
dp[c-'a']++;
if ((dp0[c-'a'] > 0) && (dp[c-'a'] <= dp0[c-'a'])) count++;
if (i >= k) {
c = s.charAt(i-k);
dp[c-'a']--;
if (dp[c-'a'] < dp0[c-'a']) count--;
}
if (count == k) ret.add(i-k+1);
}
return ret;
}
Problem: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
In this problem, we need to find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1: Input: s = "aaabb", k = 3/ Output: 3
The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2: Input: s = "ababbc", k = 2/ Output: 5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
For this problem:
public int longestSubstring(String s, int k) {
int d = 0;
for (int numUniqueTarget = 1; numUniqueTarget <= 26; numUniqueTarget++) {
d = Math.max(d, longestSubstringWithNUniqueChars(s, k, numUniqueTarget));
}
return d;
}
private int longestSubstringWithNUniqueChars(String s, int k, int numUniqueTarget) {
int[] map = new int[256];
int numUnique = 0; // counter 1
int numAtLeastK = 0; // counter 2
int i = 0, d = 0;
for (int j = 0; j < s.length(); j++) {
if (map[s.charAt(j)]++ == 0) numUnique++; // increment map[c] after this statement
if (map[s.charAt(j)] == k) numAtLeastK++; // inc end after this statement
while (numUnique > numUniqueTarget) {
if (map[s.charAt(i)]-- == k) numAtLeastK--; // decrement map[c] after this statement
if (map[s.charAt(i)] == 0) numUnique--; // inc begin after this statement
i++;
}
// if we found a string where the number of unique chars equals our target
// and all those chars are repeated at least K times then update max
if (numUnique == numUniqueTarget && numUnique == numAtLeastK)
d = Math.max(j-i+1, d);
}
return d;
}
Problem: https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/
In this problem, there are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints. In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards. Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
This is a pretty clever problem. Finding K problems from the two edges is equivalent to the problem of finding (N-K) problems in the middle. So, we can do a sliding window for (N-K) and look for the max of (total_sum - sum(N-K) elements)
class Solution {
int ret = 0;
public int maxScore(int[] a, int k) {
int tot = 0;
for (int elem: a) tot += elem;
int cur = 0, ret = 0;
k = a.length -k;
for (int i = 0; i < a.length; i++) {
cur += a[i];
if (i < k) {
if (i == k-1) {
ret = Math.max(ret, tot - cur);
}
} else {
cur -= a[i-k];
ret = Math.max(ret, tot - cur);
}
}
return ret;
}
}