➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program
Sliding Windows and Two Pointers | Sliding Window efficiently finds the maximum or minimum sum of k consecutive elements by maintaining a dynamic subarray, reducing complexity to O(n). Two Pointers uses two indices to traverse and solve problems on sorted arrays in O(n) time, ideal for finding pairs or subarrays meeting specific conditions.
Table of Contents
- Longest Substring Without Repeating Characters
- Max Consecutive Ones III
- Fruit Into Baskets
- Longest Repeating Character Replacement
- Minimum Size Subarray Sum
- Subarray Sum at Most k Distinct
- Number of Substrings Containing All Three Characters
- Maximum Points You Can Obtain from Cards
- Minimum Window Substring
- Number of Subarrays with Bounded Maximum
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters. Problem: 3.
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int res = 0, start = 0;
for(int end=0; end<s.length(); end++){
char ch =s.charAt(end);
if(map.containsKey(ch)){
if(start<=map.get(ch)){
start = map.get(ch) + 1;
}
}
res = Math.max(res, end-start+1);
map.put(ch, end);
}
return res;
}
}Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s. Problem: 1004.
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Hints:-
- One thing’s for sure, we will only flip a zero if it extends an existing window of 1s. Otherwise, there’s no point in doing it, right? Think Sliding Window!
- Since we know this problem can be solved using the sliding window construct, we might as well focus in that direction for hints. Basically, in a given window, we can never have > K zeros, right?
- We don’t have a fixed size window in this case. The window size can grow and shrink depending upon the number of zeros we have (we don’t actually have to flip the zeros here!).
- The way to shrink or expand a window would be based on the number of zeros that can still be flipped and so on.
class Solution {
public int longestOnes(int[] arr, int k) {
int count1 = 0, count0=0, max = 0, n = arr.length;
for (int i = 0, s = 0; i < n; i++) {
if (arr[i] == 1) {
count1++;
} else {
count0++;
}
if (count0 <= k) {
max = Math.max(max, count1 + count0);
} else {
if (arr[s++] == 1) {
count1--;
} else {
count0--;
}
}
}
return max;
}
}Fruit Into Baskets
This problem is also known as the length of a contiguous subarray with at most 2 distinct integers. Problem: 904. Solution.
class Solution {
public int totalFruit(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
int j = 0, res = 0;
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
if (map.size() > 2) {
if (map.get(arr[j]) > 1) {
map.put(arr[j], map.get(arr[j]) - 1);
} else {
map.remove(arr[j]);
}
j++;
}
res = Math.max(res, i - j + 1);
}
return res;
}
}Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations. Problem: 424.
class Solution {
public int characterReplacement(String s, int k) {
int[] freq = new int[26];
int maxFreq = 0, maxWindow = 0, l=0;
for(int i=0; i<s.length(); i++){
freq[s.charAt(i) - 'A']++;
maxFreq = Math.max(maxFreq, freq[s.charAt(i) - 'A']);
int windowLen = i-l+1;
while(windowLen - maxFreq > k){
// reduce window
freq[s.charAt(l++) - 'A']--;
}
windowLen = i-l+1;
maxWindow = Math.max(maxWindow, windowLen);
}
return maxWindow;
}
}Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead. Problem: 209
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int min = Integer.MAX_VALUE, l = 0, cs = 0;
for(int r=0; r<nums.length; r++){
cs += nums[r];
while (cs >= target) {
min = Math.min(min, r - l + 1);
cs -= nums[l++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}Subarray Sum at Most k Distinct
We need to calculate the number of subarrays with a sum exactly k, not at most k. If we calculate the number of subarrays with sum at most k and at most k-1, their difference would give us the number of subarrays with sum exactly k.
Longest Substring with At Most K Distinct Characters
You are given a string ‘str’ and an integer ‘K’. Your task is to find the length of the largest substring with at most ‘K’ distinct characters. For example: You are given ‘str’ = ‘abbbbbbc’ and ‘K’ = 2, then the substrings that can be formed are [‘abbbbbb’, ‘bbbbbbc’]. Hence the answer is 7. GFG, Code360, LeetCode
public class Solution {
public static int kDistinctChars(int k, String str) {
int l = 0, r = 0, maxLength = 0;
Map<Character, Integer> map = new HashMap<>();
while (r < str.length()) {
map.put(str.charAt(r), map.getOrDefault(str.charAt(r), 0) + 1);
while (map.size() > k) {
Character ch = str.charAt(l);
if (map.get(ch) > 1) {
map.put(ch, map.get(ch) - 1);
} else {
map.remove(ch);
}
l++;
}
if(map.size() == k){
maxLength = Math.max(maxLength, r - l + 1);
}
r++;
}
return maxLength;
}
}Binary Subarrays With Sum
Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal. A subarray is a contiguous part of the array. Problem: 930.
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:-
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
This problem is sub set of Count Subarray with Given Sum so that solution will also work, and it took O(n) time complexity and O(n) space complexity. However there are some better solutions to reduce space complexity. For that we can use Sliding Window. Solution.
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
return numSubarrays(nums, goal) - numSubarrays(nums, goal - 1);
}
public int numSubarrays(int[] nums, int goal) {
if (goal < 0) {
return 0;
}
int l = 0, r = 0, count = 0, sum = 0;
while (r < nums.length) {
sum += nums[r];
while (sum > goal) {
sum -= nums[l++];
}
count += r - l + 1;
r++;
}
return count;
}
}Count Number of Nice Subarrays
Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays. Problem: 1248.
Hint: After replacing each even by zero and every odd by one, the problem becomes exactly similar to the previous one.
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
return countSubArray(nums, k) - countSubArray(nums, k - 1);
}
public int countSubArray(int[] nums, int k) {
if (k < 0) {
return 0;
}
int l = 0, r = 0, count = 0, sum = 0;
while (r < nums.length) {
sum += nums[r] % 2;
while (sum > k) {
sum -= nums[l++] % 2;
}
count += r - l + 1;
r++;
}
return count;
}
}Subarrays with K Different Integers
Given an integer array nums and an integer k, return the number of good subarrays of nums. A good array is an array where the number of different integers in that array is exactly k. For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3. A subarray is a contiguous part of an array. Problem: 992. Solution.
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
return subarray(nums, k) - subarray(nums, k - 1);
}
public int subarray(int[] nums, int k) {
int l = 0, r = 0, count = 0;
Map<Integer, Integer> map = new HashMap<>();
while (r < nums.length) {
map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
while (map.size() > k) {
int ele = nums[l];
if (map.get(ele) > 1) {
map.put(ele, map.get(ele) - 1);
} else {
map.remove(ele);
}
l++;
}
count += r - l + 1;
r++;
}
return count;
}
}Substrings with K Distinct Characters
Given a string s of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters. Problem
Input: s = “aba”, k = 2
Output: 3
Explanation: The substrings are: “ab”, “ba” and “aba”.
import java.util.HashMap;
import java.util.Map;
public class Test {
public static void main(String[] args) {
String str = "aba";
System.out.println(countSubstrWithKDistinct(str, 2));
}
static int countSubstrWithKDistinct(String s, int k) {
return countSubstrWithAtMostKDistinct(s, k) - countSubstrWithAtMostKDistinct(s, k - 1);
}
static int countSubstrWithAtMostKDistinct(String s, int k) {
if (k == 0) {
return 0;
}
Map<Character, Integer> freq = new HashMap<>();
int count = 0, start = 0;
for (int end = 0; end < s.length(); end++) {
freq.compute(s.charAt(end), (key, v) -> v == null ? 1 : v + 1);
while (freq.size() > k) {
freq.computeIfPresent(s.charAt(start), (key, v) -> v == 1 ? null : v - 1);
start++;
}
count += end - start + 1;
}
return count;
}
}Number of Substrings Containing All Three Characters
Given a string s consisting only of characters a, b and c. Return the number of substrings containing at least one occurrence of all these characters a, b and c. Problem: 1358. Solution.
Input: s = “abcabc”
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” and “abc” (again).
class Solution {
public int numberOfSubstrings(String s) {
int[] lastSeen = { -1, -1, -1 };
int count = 0;
for (int i = 0; i < s.length(); i++) {
lastSeen[s.charAt(i) - 'a'] = i;
count += 1 + Math.min(lastSeen[0], Math.min(lastSeen[1], lastSeen[2]));
}
return count;
}
}Maximum Points You Can Obtain from Cards
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. Problem: 1423. Solution.
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. Your score is the sum of the points of the cards you have taken. Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
class Solution {
public int maxScore(int[] cardPoints, int k) {
int lsum = 0, rsum = 0, max = 0;
for(int i=0; i<k; i++){
lsum += cardPoints[i];
}
max = lsum;
for(int i=k-1, j=cardPoints.length-1; i>=0; i--, j--){
lsum -= cardPoints[i];
rsum += cardPoints[j];
max = Math.max(max, lsum + rsum);
}
return max;
}
}Minimum Window Substring
Given two strings s and t of lengths m and n respectively, 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 “”. Problem: 76.
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) {
return "";
}
int[] map = new int[128];
int count = t.length();
int start = 0, end = 0, minLen = Integer.MAX_VALUE, startIndex = 0;
for (char c : t.toCharArray()) {
map[c]++;
}
char[] chS = s.toCharArray();
while (end < chS.length) {
if (map[chS[end]]-- > 0) {
count--;
}
while (count == 0) {
if (end - start < minLen) {
startIndex = start;
minLen = end - start;
}
if (map[chS[start]]++ == 0) {
count++;
}
start++;
}
end++;
}
return minLen == Integer.MAX_VALUE ? "" :
s.substring(startIndex, startIndex + minLen + 1);
}
}Number of Subarrays with Bounded Maximum
Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right]. Problem: 795. Solution.
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7
class Solution {
public int numSubarrayBoundedMax(int[] nums, int left, int right) {
int res = 0;
int start = -1, end = -1;
for(int i=0; i<nums.length; i++){
if(nums[i] > right) {
start = i;
end = i;
} else if(nums[i] >= left){
end = i;
}
res += end - start;
}
return res;
}
}If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!