Find the Smallest Subarray Covering All Values

EPI 13.7

Description:

Write a program which takes an array of strings and a set of strings, and return the indices of the starting and ending index of a shortest subarray of the given array that "covers" the set, i.e., contains all strings in the set.

Example:

string arr
{"apple", "banana", "apple", "apple", "dog", "cat", "apple", "dog", "banana", "apple", "cat", "dog"}
set:
{"banana", "cat"}

Idea:

Similar to "minimal length of a contiguous subarray of which the sum ≥ s".

双指针加hashmap

Time O(n)

Code:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

int smallestDistSubarray(vector<string> arr, vector<string> stringSet){
    unordered_map<string, int> visitedSet;
    int totalCount = 0;
    int j=0; // left pointer
    int left, right;
    int minLen=INT_MAX;
    for(auto elem: stringSet){
        visitedSet[elem] = 0;
    }

    for(int i=0; i<arr.size(); i++){  // right pointer
        if(visitedSet.find(arr[i])!=visitedSet.end() && visitedSet[arr[i]]==0){
            totalCount++;
            visitedSet[arr[i]]++;
        }

        while(totalCount==stringSet.size()){
            if(visitedSet.find(arr[j])!=visitedSet.end() && --visitedSet[arr[j]]==0){
                totalCount--;
                if(minLen>i-j+1){
                    minLen=i-j+1;
                    left=j;
                    right=i;
                    cout<<left<<' '<<right<<' '<<minLen<<endl;
                }
            }
            j++;
        }
    }

    return minLen;
}

int main(){
    vector<string> arr = {"apple", "banana", "apple", "apple", "dog", "cat", "apple", "dog", "banana", "apple", "cat", "dog"};
    vector<string> stringSet = {"banana", "cat"};

    cout<<smallestDistSubarray(arr, stringSet);
}