Template:
for (i = 0; i < n; i++) {
while (j < n && condition_j) {
update condition_j with j;
j++;
//update rst;
}
//if (!condition_j) {
// update rst;
//}
update condition_j with i;
}
public int minimumSize(int[] nums, int s) {
// write your code here
int i = 0;
int j = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
for (i = 0; i < nums.length; i++) {
while (j < nums.length && sum < s) {
sum += nums[j];
j++;
}
if (sum >= s) {
min = Math.min(min, j - i);
}
sum -= nums[i];
}
if (min == Integer.MAX_VALUE) return -1;
return min;
}
public int lengthOfLongestSubstring(String s) {
// write your code here
Set<Character> set = new HashSet<>();
int i = 0;
int j = 0;
int max = 0;
for (i = 0; i < s.length(); i++) {
while (j < s.length() && !set.contains(s.charAt(j))) {
set.add(s.charAt(j));
j++;
max = Math.max(j - i, max);
}
set.remove(s.charAt(i));
}
return max;
}
Minimum Size Subarray Sum
- pos + len <= nums.length
- strStr, two pointers, i -> [0, sourceLen - targetLen] <=> pos + targetLen <= sourceLen
class Solution {
public int minSubArrayLen(int s, int[] nums) {
for (int len = 1; len <= nums.length; len++) {
for (int pos = 0; pos + len <= nums.length; pos++) {
int sum = getSum(pos, len, nums);
if (sum >= s) return len;
}
}
return 0;
}
private int getSum(int pos, int len, int[] nums) {
int sum = 0;
for (int i = 0; i < len; i++) {
sum += nums[i + pos];
}
return sum;
}
}
- two pointers
see above
minimum window substring:
public class Solution {
public String minWindow(String source , String target) {
// write your code here
int i = 0;
int j = 0;
int[] count = new int[256];
int distinct = 0;
int min = Integer.MAX_VALUE;
String rst = source;
for (int a = 0; a < target.length(); a++) {
count[target.charAt(a)]++;
if (count[target.charAt(a)] == 1) distinct++;
}
for (i = 0; i < source.length(); i++) {
while (j < source.length() && !containsAll(distinct, count[source.charAt(j)])) {
count[source.charAt(j)]--;
if (count[source.charAt(j)] == 0) distinct--;
j++;
}
if (containsAll(distinct, count[source.charAt(j-1)])) {
if (j - i < min) {
min = j - i;
rst = source.substring(i, j);
}
count[source.charAt(i)]++;
if (count[source.charAt(i)] == 1) distinct++;
}
}
return min == Integer.MAX_VALUE? "" : rst;
}
private boolean containsAll(int distinct, int element) {
return distinct == 0 && element <= 0; // negative element is still valid
}
}
Longest Substring Without Repeating Characters
- approach 1: use while() to pop out each element until the repeated element
- approach 2: use map to directly locate the last occurence of repeated element.
see above
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
longest substring with at most two distinct character:
- x approach 1 has problem: b/c
aaabbbbcccc, it will stop at the second c instead of the first c - approach 2 is correct
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
int[] hash = new int[128];
int count = 0;
int start = 0;
int end = 0;
int maxLen = 0;
while (end < s.length()) {
while (end < s.length() && count < 3) {
maxLen = Math.max(maxLen, end - start + 1);
hash[s.charAt(end)]++;
if (hash[s.charAt(end)] == 1) count++; // means from none to exist
end++;
}
if (count < 3) break;
while (start < end && count >= 3) {
hash[s.charAt(start)]--;
if (hash[s.charAt(start)] == 0) count--; // means from exist to none
start++;
}
}
return maxLen;
}
}
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if(s.length() < 1) return 0;
HashMap<Character,Integer> index = new HashMap<Character,Integer>();
int lo = 0;
int hi = 0;
int maxLength = 0;
while(hi < s.length()) {
if(index.size() <= 2) {
char c = s.charAt(hi);
index.put(c, hi);
hi++;
}
if(index.size() > 2) {
int leftMost = s.length();
for(int i : index.values()) {
leftMost = Math.min(leftMost,i);
}
char c = s.charAt(leftMost);
index.remove(c);
lo = leftMost+1;
}
maxLength = Math.max(maxLength, hi-lo);
}
return maxLength;
}
}
longest substring with at most k distinct characters
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
Map<Character, Integer> map = new HashMap<>();
int i = 0;
int j = 0;
int max = 0;
for (i = 0; i < s.length(); i++) {
while (j < s.length() &&
((map.size() <= k && map.containsKey(s.charAt(j))) || (map.size() < k && !map.containsKey(s.charAt(j))))
) {
int count = map.getOrDefault(s.charAt(j), 0) + 1;
map.put(s.charAt(j), count);
j++;
max= Math.max(j - i, max);
}
// while (j < s.length()) {
// char c = s.charAt(j);
// int count = 1;
// if (map.containsKey(c)) {
// count = map.get(c) + 1;
// map.put(c, count);
// } else {
// if (map.size() == k) break;
// map.put(c, count);
// }
// // if (map.size() == k) break;
// // int count = map.getOrDefault(s.charAt(j), 0) + 1;
// // map.put(s.charAt(j), count);
// j++;
// max= Math.max(j - i, max);
// }
// char c = s.charAt(i);
// if(map.containsKey(c)){
// int count = map.get(c);
// if (count > 1) {
// map.put(c, count - 1);
// } else {
// map.remove(c);
// }
// }
int count = map.getOrDefault(s.charAt(i), 0) - 1;
map.put(s.charAt(i), count);
if (count <= 0) {
map.remove(s.charAt(i));
}
}
return max;
}
}
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int[] count = new int[256]; // there are 256 ASCII characters in the world
int i = 0; // i will be behind j
int num = 0;
int res = 0;
for (int j = 0; j < s.length(); j++) {
if (count[s.charAt(j)]++ == 0) { // if count[s.charAt(j)] == 0, we know that it is a distinct character
num++;
}
while (num > k && i < s.length()) { // sliding window
count[s.charAt(i)]--;
if (count[s.charAt(i)] == 0){
num--;
}
i++;
}
res = Math.max(res, j - i + 1);
}
return res;
}