algorithm-examples/cpp-algorithm/src/hashtable/smallest_subarray.h at main · codejsha/algorithm-examples · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#ifndef CPP_ALGORITHM_SMALLEST_SUBARRAY_H
#define CPP_ALGORITHM_SMALLEST_SUBARRAY_H

#include <limits>
#include <string>
#include <unordered_map>
#include <vector>

namespace SmallestSubarray
{
    /**
     * \brief Find the smallest subarray that covers all the elements in a set.
     * \param paragraph an array
     * \param keywords a set
     * \return a tuple of the start and end indices of the smallest subarray
     */
    std::tuple<int, int> FindSmallestSubarrayCoveringSubset(
        const std::vector<std::string>& paragraph,
        const std::vector<std::string>& keywords);

    /**
     * \brief Find the smallest subarray that sequentially covers all the elements in a set.
     * \param paragraph an array
     * \param keywords a set
     * \return a tuple of the start and end indices of the smallest subarray
     */
    std::tuple<int, int> FindSmallestSubarraySequentiallyCoveringSubset(
        const std::vector<std::string>& paragraph,
        const std::vector<std::string>& keywords);
}

// ----------------------------------------------------------------------------
inline std::tuple<int, int> SmallestSubarray::FindSmallestSubarrayCoveringSubset(
    const std::vector<std::string>& paragraph,
    const std::vector<std::string>& keywords)
{
    // keep track of the number of keywords that have been covered
    std::unordered_map<std::string, int> keywords_to_cover;
    for (const std::string& keyword : keywords)
    {
        ++keywords_to_cover[keyword];
    }

    std::tuple<int, int> result = std::make_tuple(-1, -1);
    size_t remaining_to_cover = keywords.size();

    for (int left_index = 0, right_index = 0; right_index < static_cast<int>(paragraph.size()); ++right_index)
    {
        // decrement the number of keywords that need to be covered
        const std::string& right_word = paragraph[right_index];
        if (const auto it = keywords_to_cover.find(right_word);
            it != keywords_to_cover.end())
        {
            --it->second;
            if (it->second >= 0)
            {
                --remaining_to_cover;
            }
        }

        // advance left pointer until keywords_to_cover does not contain all keywords
        while (remaining_to_cover == 0)
        {
            // if result is not set yet
            // or the current subarray is smaller than the current result
            if (std::get<0>(result) == -1
                || right_index - left_index < std::get<1>(result) - std::get<0>(result))
            {
                result = std::tuple{left_index, right_index};
            }

            // increment the number of keywords that need to be covered
            const std::string& left_word = paragraph[left_index];
            if (const auto it = keywords_to_cover.find(left_word);
                it != keywords_to_cover.end())
            {
                ++it->second;
                if (it->second > 0)
                {
                    ++remaining_to_cover;
                }
            }

            ++left_index;
        }
    }

    return result;
}

// ----------------------------------------------------------------------------
inline std::tuple<int, int> SmallestSubarray::FindSmallestSubarraySequentiallyCoveringSubset(
    const std::vector<std::string>& paragraph,
    const std::vector<std::string>& keywords)
{
    // map each keyword to its index in the keywords vector
    std::unordered_map<std::string, int> keywords_to_index;
    for (int i = 0; i < static_cast<int>(keywords.size()); ++i)
    {
        keywords_to_index[keywords[i]] = i;
    }

    std::vector<int> last_occurrence = std::vector(keywords.size(), -1);
    std::vector<int> shortest_subarray_length = std::vector(keywords.size(), std::numeric_limits<int>::max());

    int shortest_distance = std::numeric_limits<int>::max();
    std::tuple<int, int> result = std::make_tuple(-1, -1);

    for (int i = 0; i < static_cast<int>(paragraph.size()); ++i)
    {
        if (const std::string& word = paragraph[i];
            keywords_to_index.contains(word))
        {
            const int keyword_index = keywords_to_index.find(word)->second;

            // if keyword is the first one in the keywords vector
            if (keyword_index == 0)
            {
                shortest_subarray_length[keyword_index] = 1;
            }
            // if the shortest subarray length of the previous keyword is not infinite
            else if (shortest_subarray_length[keyword_index - 1] != std::numeric_limits<int>::max())
            {
                const int distance_to_previous_keyword = i - last_occurrence[keyword_index - 1];
                shortest_subarray_length[keyword_index] =
                    distance_to_previous_keyword + shortest_subarray_length[keyword_index - 1];
            }
            last_occurrence[keyword_index] = i;

            // if the current keyword is the last one
            // and its shortest subarray length is smaller than the current shortest distance
            if (keyword_index == static_cast<int>(keywords.size()) - 1
                && shortest_subarray_length.back() < shortest_distance)
            {
                shortest_distance = shortest_subarray_length.back();
                result = std::tuple{i - shortest_distance + 1, i};
            }
        }
    }

    return result;
}

#endif