CareerCup

the 2 data structures are a list (for O(n) insertion) & a hash-map that keys the list elements.
insert requires a list traversal bcz hashmap doesnt maintain ordering, so we cannot search an adjacent item.
once we insert the item into the list, we update the hash-map so a lookup will yield the pointer to that object.
delete requires lookup using hash-map (O(1), followed by the removal of entry from hash-map (O(1) & then unlink of object from list (O(1)

a linear time solution
---------------------------
* can we check the word from the map without scanning the whole input string (which might be order of magnitude longer) ?
* assume w is word from map, str is input.
* if we could go from the w[k] to the w[k+1] on the input string in O(1), that would fix it all.
* we can do that with pre-processing of the input string into a matrix.
* row per character in alphabet, so 256 rows.
* column per character
* pre-processing:
* for each character (c) of input string in index K, we mark it in the map @ [c,k].
* we also scan the row towards column 0 until we hit another occurrence of that character. for every column we scanned, we find the letter & point from it to the column in which c appears.
* this ensures that from a given offset, we can get the offset of any other character in O(1)
* the preprocessing time is O(256 * input string) which is linear time, although actual constant would rarely be that large.

#include <string>
#include <array>
#include <vector>
#include <unordered_set>
#include <cassert>

using namespace std;

#define NUM_MAT_ROWS		256
typedef unordered_set<string>				map_t;
typedef array<size_t, NUM_MAT_ROWS>			per_char_info_t;
struct input_char_next {
	per_char_info_t				next;		// point to the next offset of character 'c' at offset 'c'.

input_char_next()
{
	fill(next.begin(), next.end(), -1/*poison => no such character in higher offset*/);
}
};
typedef vector<input_char_next>				input_md_t;	// lookup information per character input string




class my_algorithm {
protected:
input_md_t		str_lookup;
size_t			n_col;	// No. of matrix columns


void prepare_matrix(const string	&str)
{
	for (int offset = 0; offset < str.size(); ++offset) {
		char ch = str[offset];
		struct input_char_next &elem = str_lookup[offset];
		// initialize pointing from previous characters to this one
		ssize_t prev = offset;
		do {
			prev--;
			struct input_char_next &pre = str_lookup[prev];
			pre.next[ch] = offset;
		} while ((prev >= 0) && (str[prev] != ch));
	}
}

public:
my_algorithm()
{}

const string *
find_longest_dict_word_by_del_from_input(const string	&str,
										 const map_t	&map)
{
	const string	*res = nullptr;

	// preprocessing
	n_col = str.size();
	str_lookup.resize(str.size());
	prepare_matrix(str);

	for (auto wit = map.begin(); wit != map.end(); ++wit) {
		if (wit->size() == 0) {
			continue;	// not sure what to do with empty string - they can always be matched :)
		}
		const string 	&w = *wit;   		// this is the word we attempt to match in the input string
		char			first_ch = w[0];
		size_t			curr_offset = (first_ch == str[0]) ? 0 : str_lookup[0].next[first_ch];		// offset with which we move forward on input string as we match characters.
		auto	cit = w.begin();
		for (++cit; (cit != w.end()) && (curr_offset != -1); ++cit) {
			curr_offset = str_lookup[curr_offset].next[*cit];
		}
		if (curr_offset != -1) {
			// the word can be made from input string - check if its longer than what we already found
			if (!res || (w.size() > res->size())) {
				res = &w;	// we found a longer match
			}
		}
	}
	return res;
}
};

int main ()
{
	my_algorithm	alg;
	const string	*res;

	{	// map is empty
		const map_t	map;
		res = alg.find_longest_dict_word_by_del_from_input("abpcplea", map);
		assert(res == nullptr);
	}

	{	// input string is empty
		const map_t	map = {"eitan"};
		res = alg.find_longest_dict_word_by_del_from_input("", map);
		assert(res == nullptr);
	}

	{
		const map_t	map = {"ale", "apple", "monkey", "plea"};
		res = alg.find_longest_dict_word_by_del_from_input("abpcplea", map);
		assert(*res == "apple");
	}

	{	// longest match isnt first & is also on end of input string
		const map_t	map = {"ale", "apple", "monkey", "plea"};
		res = alg.find_longest_dict_word_by_del_from_input("abpcpleamonkey", map);
		assert(*res == "monkey");
	}

	return 0;
}

push all edges into a map - the key represent both items, as a pair.
now iterate over map & for each element, search the reverse in the same map.
if its found, we have the reverse.

overall runtime is linear time bcz map is O(1) per operation.
scan is on map so it naturally eliminates duplicates from input - bcz these are eliminated when we push them to the map (unique key)