Novel solution to “substring with concatenation of all words”

Question

This is a Leetcode problem:

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

A couple of sample inputs/outputs:

s = "barfoobarthefoobarman"
words = ["bar","foo","the"]
output = [3,6,9]

s = "lingmindraboofooowingdingbarrwingmonkeypoundcake"
words = ["fooo","barr","wing","ding","wing"]
output = [13]

My code

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> answer;
        int slen = s.length(), wlen = words[0].length(), wnum = words.size();
        auto start = words.begin(), end = words.end(), bound = start, found = end;
        // traverse every possible offset with respect to wlen
        for (int i = 0; i < wlen; ++i) {
            // [bound] delineates the separation between two sections of the word list
            // left of [bound] are the words that have been found so far - I'll call this section words(found)
            // [bound] to [end] are words still to be found - I'll call this words(left)
            // I'll use words(found) as a virtual queue, pushing words on as they're found, popping expired found words
            bound = start;
            // traverse consecutive word-length substrings from offset i
            // terminate when the number of positions left to check < number of words left to find
            for (int j = i; j <= slen-wlen*(end-bound); j += wlen) {
                // look for substring first in words(left)
                auto found = std::find(bound, end, s.substr(j, wlen));
                if (found != end) {
                    std::iter_swap(found, bound++); // 'push' [found] onto words(found)
                } else {
                    // if substring not found in words(left), look in words(found)
                    found = std::find(start, bound, s.substr(j, wlen));
                    if (found != bound) {
                        // if the substring is one of the words(found),
                        // we need to 'pop' all words up to and including [found] from words(found)
                        // (which we can do using a rotation) and push [found] back onto the end
                        std::iter_swap(found, bound); // pushing first is simpler
                        bound = std::rotate(start, found+1, bound+1); // pop
                    } else {
                        // if current substring is not in the word list at all, reset words(found) to nil
                        bound = start;
                    }
                }
                if (bound == end) {
                    // if words(found) == [words], we've found an answer! push it on
                    answer.push_back(j-wlen*(wnum-1));
                    std::rotate(start, start+1, bound--); // pop first word off words(found)
                }
            }
        }
        return answer;
    }
};

Explanation

In my solution, the intuition is that as I loop through consecutive word positions (ie. incrementing by word length), building up a concatenation of words, I need to keep track of words I've found so far in a queue. If the substring I'm looking at is one of the words I'm yet to find, I push it onto the queue. Otherwise, if it's a word that's already in my concatenation-so-far, I need to pop everything off the queue up to and including that word, then push it back onto the end. (Think about the sample input above when I encounter "foobarfoo".) If it's not a word at all, clear the queue.

Rather than creating a queue, though, I construct a 'virtual' one in-place, using an iterator to mark the division in the list words between words-found and words-still-to-find. This way, when I 'pop' words by rotating words and repositioning the iterator, those words automatically end up in the words-still-to-find side of the list.

Discussion

I haven't seen a solution like this posted on the site. Most of them use one or two unordered_maps, but from what I can see they either don't iterate through word-positions like I am, or they don't address the queue-like nature of doing so. Using some kind of hashmap definitely improves efficiency, but my solution remains competitive (beating 70% of C++ submissions, at 48ms) because of its lack of overheads and efficient iteration (I think). As a bonus, it has constant space complexity.

Questions:

1. Am I right in thinking the time complexity is \$O(n)\$?
2. Does this approximate a known algorithm?
3. Is there a more appropriate data structure I could be using here? I want to introduce a hashmap whose values somehow point to a queue, but I can't figure out how to make all the pieces fit.

Answer 1

General observations

• Consider function-level comments. Your code has a dependency on the problem description to understand what it intends to do. It would be nice for this to be self-contained.
• Avoid redundant code. On line 6 you initialize several variables, including bound = start. Then just inside the outer for loop you reinitialize it the same way. Similarly in both of your calls to find, you create an identical temporary s.substr(j, wlen).
• Avoid shadowing variables. On line 6 you create and initialize found = end, but then on line 18 (just inside the inner for loop) you create a new found = std::find(...).
• Strongly consider splitting your declarations onto multiple lines; instead of of creating slen, wlen, and wnum all on line 5, use three lines to create them one each; this makes it easier to scan for their creation.
• Mark constants const. It looks like slen, wlen, wnum, start, and end are all used in immutable ways. By marking them const, you communicate this directly, and avoid potential mistakes that modify them.

Computational complexity

When I first started scanning your code to assess your question of linear complexity (linear on what?), I was skeptical. Your code has two nested for loops that appear to do linear scans. Within the inner for loop, there are calls to std::find and std::rotate which each have linear complexity on their own. So before analyzing bounds that reduce things, this appears to be possibly cubic: O(n • m • (f₁ +f₂ + r₁ + r₂)).

From there we can reduce things a lot. What are n, m, f₁, f₂, r₁, and r₂ here, and what does that give us? For clarity, I'll call the inputs S: the length of the scanned string, W: the number of words, and L: the length of each words. This lets us specify the others as follows:

• n = L; the outer loop is a function of the length of the words, irrespective of the length S or the count W
• m = S / L; the inner loop is a function of the length S and word length L

So already we can simplify to O(S • (f₁ + f₂ + r₁ + r₂))

• f₁ + f₂ = W • L; the search in std::find is linear on the count of elements (W total for both finds), and the comparison is linear on the word length L. (There's also an additional L charge for creating the temporary substring, but that constant multiplier falls out.) You need to consider both W and L, because a worst case list of words may include things that mismatch all on the final letter, like "aa…aab", "aa…aac", "aa…aad", …. It's possible that we might need to subdivide f₁ and f₂ if they contribute different weights, but I don't expect so.

• r₁ is linear on the distance rotated, i.e. bound - start. All we know is that we don't have all words, so this is maxed out at the word count W.

• r₂ is also linear on bound - start. Since we know bound is approximately end, and thus the rotate always costs W - 1 moves.

So this simplifies further to O(S • (W • L + W + W)) = O(S • W • (L + 2)), which in turn is O(S • W • L). I think it's reasonable to conversationally consider W • L to be collectively linear (as together they're the quantity of characters in words). So, I would feel pretty comfortable calling quadratic, even though the nature of O(S • W • L) doesn't lend itself well to being called linear, quadratic, or cubic. I guess it's technically linear on any one of those three inputs... ??

In summary, I would say this is not linear. It depends on all factors of the input, though arguably only two of them scale independently. You could rephrase the above using D, the total size in characters of your words dictionary: D = W • L, thus the complexity could be called O(S • D). For linear I would want that to be O(S + D)

Kudos

I do like how your implementation's added space complexity is constant. There's definitely a lot of advantage to this. It's unclear how legit it is reorder the contents of the vector, but let's stick with the assumption that it's okay.

Further optimization ideas

So, given the above, what can we make incrementally better? Note that none of this is likely to really change the performance characteristics of your code, so only make these changes when they make things easier to read, or a profiler shows that you need the improvement and that it improves things.

• Avoid creating temporary substrings. Instead of calling std::find(a, b, s.substr(j, wlen)), consider using a std::string_view (C++17) or std::find_if with a predicate that doesn't have to copy the characters (such as one built on std::search or std::mismatch). In practice, as long as L is small, this will likely be inconsequential due to small string optimization (SSO).
• Consider using data structures that don't require linear updates, such as std::deque. The biggest downside here is that it will result in extra space consumption bounded at around W • L.
• Alternately, consider sorting the words that haven't yet been found. Then, instead of using a linear searching std::find, you can use the binary searching std::lower_bound. This would make computational complexity much harder to analyze, but I expect the worst case remains the same. (There's additional cost for sorting, and for maintaining the sort as words return, but reduced cost various scenarios.) And in practice, depending on the sizes involved, linear searches can outperform binary searches due to caching and branch prediction effects, so it may or may not be a win for small counts.
• Consider both the extra data structure for tracking found words, and sorting the list of words.
• Consider throwing out special cases that could perform badly, such as when S < W • L. Your code mostly does this, but it has to do it L times. And it already nicely discards the case where L is 0.
• Consider what should happen if an element in words is repeated. I think your code handles this in a well-defined fashion. Bonus kudos! It might be worth noting this in your comments. (Or in the problem description...)

Similar algorithms, alternate data structures

Other than that this sounds generically like a sliding window algorithm, I don't know of anything that this specifically matches.

If you want to have a map that points to a queue, I might suggest something like a std::unordered_map<string, size_type>, where you store an insertion-order index into the queue. If you also track the number of times you have popped from the front, and then you can determine if an index is stale, or how far to offset the index when looking inside the queue. Pointers and iterators directly to the items in the queue are likely unsafe, as modifying the queue can invalidate them.