https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/ is very similar
Q1: you are given a list of (possibly repeating) words denoted L that are all the same length , and a long string denoted S. Find a substring of S that is a concatenation of each word in the list exactly once and without any intervening characters. Such a substring is known as a dragon.
To simplify the problem, you can assume it occurs at least once in the sentence.
L: “fooo”, “barr”, “wing”, “ding”, “wing”.
Answer — fooowingdingbarrwing.
For O(), let’s assume there are H characters in haystack, W characters in each word, and N words (possibly repeating)
Q1b: what if word length is not uniform?
Solution-A — See https://github.com/tiger40490/repo1/blob/py1/py/str/dragonSearch.py with O(HN)
I hope this can be adapted for Q1b — see source comments
Solution-B1 (Brute force) — For each permutation, scan by indexOf() or strstr() or string::find(). Guaranteed to find a solution in finite time. Doable if N is small, since there’s O(N!) element.
Solution-B2 (Brute force) — WN-long sliding window over haystack. Each window is examined to determine if it’s a dragon.
This is reasonable if H is small relative to N.
Solution-C — a potentially faster solution if the list is large — Permutation of 5 would be 120 😦
Phase 1: For each word in the list, i’d count how many times it occurs. The word with lowest occurrence would be a “candidate”.
If every word has the same occurrence (say 3), I think this is still faster than Solution-B, because all but one of the occurrences is a false positive. It’s relatively easy to screen them out.
As soon as I find a word with occurrence=1 exactly, I exit Phase 1 with a super candidate. For this discussion, I assume we have a super candidate.
Updae — In such a case, I can also use the Solution A approach. Even if the best candidate has occurrence = 2 I can consider this approach…
Phase 2a: remove the super candidate from the list. Blindly read the next 4 character in S after our super candidate. See if any word starts with that…..
Phase 2b: do the same leftward. Perhaps by reversing all the strings.