Find the smallest subarray covering all values
SmallestSubarrayCoveringSe.javapublic static Pair<Integer, Integer> findSmallestSubarrayCoveringSubset(
final List<String> A, final List<String> Q) {
Set<String> dict = new HashSet<>(Q);
Map<String, Integer> countQ = new HashMap<>();
int l = 0, r = 0;
Pair<Integer, Integer> res = new Pair<>(-1, -1);
while (r < A.size()) {
// Keeps moving r until it reaches end or countQ has |Q| items.
while (r < A.size() && countQ.size() < Q.size()) {
if (dict.contains(A.get(r))) {
countQ.put(A.get(r),
countQ.containsKey(A.get(r)) ? countQ.get(A.get(r)) + 1 : 1);
}
++r;
}
if (countQ.size() == Q.size() && // Found |Q| keywords.
((res.getFirst() == -1 && res.getSecond() == -1) || r - 1 - l < res
.getSecond() - res.getFirst())) {
res.setFirst(l);
res.setSecond(r - 1);
}
// Keeps moving l until it reaches end or countQ has less |Q| items.
while (l < r && countQ.size() == Q.size()) {
if (dict.contains(A.get(l))) {
int it = countQ.get(A.get(l));
countQ.put(A.get(l), --it);
if (it == 0) {
countQ.remove(A.get(l));
if ((res.getFirst() == -1 && res.getSecond() == -1)
|| r - 1 - l < res.getSecond() - res.getFirst()) {
res.setFirst(l);
res.setSecond(r - 1);
}
}
}
++l;
}
}
return res;
}
SmallestSubarrayCoveringSetStream.java
Use Double Linked list to store last occurence index of each keyword, and Hashmap to map each keyword to the corresponding node.
public static Pair<Integer, Integer> findSmallestSubarrayCoveringSubset(
List<String> A, List<String> Q) {
// Tracks the last occurrence (index) of each string in Q.
LinkedList<Integer> loc = new LinkedList<>();
Map<String, LinkedList<Integer>.Node> dict = new HashMap<>();
for (String s : Q) {
dict.put(s, null);
}
Pair<Integer, Integer> res = new Pair<>(-1, -1);
int idx = 0;
String s = new String();
for (String aA : A) {
s = aA;
if (dict.containsKey(s)) { // s is in Q.
LinkedList<Integer>.Node it = dict.get(s);
if (it != null) {
loc.erase(it);
}
LinkedList<Integer>.Node back = loc.pushBack(idx);
dict.put(s, back);
}
if (loc.size() == Q.size() && // Found |Q| keywords.
((res.getFirst() == -1 && res.getSecond() == -1) || idx
- loc.front().item < res.getSecond() - res.getFirst())) {
res.setFirst(loc.front().item);
res.setSecond(idx);
}
++idx;
}
return res;
}
