# Latest content was relocated to https://bintanvictor.wordpress.com. This old blog will be shutdown soon.

## Saturday, May 19, 2012

### locate in a long sentence a permutation of my favorite words

Q: Given a list of words, L, that are all the same length, and a string, S, find the starting position of the substring of S that is a concatenation of each word in L exactly once and without any intervening characters. This substring is guaranteed to occur exactly once in S.

Example:.
L: "fooo", "barr", "wing", "ding", "wing".
S: "lingmindraboofooowingdingbarrwingmonkeypoundcake".

My solutions below ignore the "same-length" constraint.

Solution-B (Brute force) -- For each permutation, scan by indexOf() or strstr(). Guaranteed to find a solution in finite time. Inefficient if list is large.

Solution-C -- a potentially faster solution.

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 occurs 2+, then I may resort to Solution-B.

I'd start with the longest word (skipping those non-unique words) in L -- assumed to be the most likely candidate. 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.

Phase 2a: remove the super candidate from the list. Find the shortest word's length in the list. Say it's 4. 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.