Find smallest subarray that sequentially covering all values
SubseqCover.javapublic static Pair<Integer, Integer> findSmallestSequentiallyCoveringSubset(
List<String> A, List<String> Q) {
// Stores the order of each Q[i].
Map<String, Integer> K = new HashMap<>();
List<Integer> L = new ArrayList<>(Q.size());
List<Integer> D = new ArrayList<>(Q.size());
// Initializes L, D, and K.
for (int i = 0; i < Q.size(); ++i) {
L.add(-1);
D.add(Integer.MAX_VALUE);
K.put(Q.get(i), i);
}
Pair<Integer, Integer> res = new Pair<>(-1, A.size());
for (int i = 0; i < A.size(); ++i) {
Integer it = K.get(A.get(i));
if (it != null) {
if (it == 0) { // First one, no predecessor.
D.set(0, 1); // Base condition.
} else if (D.get(it - 1) != Integer.MAX_VALUE) {
D.set(it, i - L.get(it - 1) + D.get(it - 1));
}
L.set(it, i);
if (it == Q.size() - 1
&& D.get(D.size() - 1) < res.getSecond() - res.getFirst() + 1) {
res.setFirst(i - D.get(D.size() - 1) + 1);
res.setSecond(i);
}
}
}
return res;
}
