Minimum window width in string x that contains all characters in string y?

This is how I would do it: Create a hash table for all the characters from string Y. (I assume all characters are different in Y) First pass: Start from first character of string X update hash table, for exa: for key 'a' enter location (say 1) Keep on doing it until you get all characters from Y (until all key in hash table has value) If you get some character again, update its newer value and erase older one Once you have first pass, take smallest value from hash table and biggest value Thats the minimum window observed so far Now, go to next character in string X, update hash table and see if you get smaller window Algorithm complexity: O(n) : One pass space: O(k) Edit: Lets take an example here: String x = "coobdafceeaxab String y = "abc First initialize a hash table from characters of Y ha = -1 hb = -1 hc = -1 Now, Start from first character of X First character is c, hc = 0 Second character (o) is not part of hash, skip it Fourth character (b), hb = 3 Sixth character(a), enter hash table ha = 5 Now, all keys from hash table has some value Smallest value is 0 (of c) and highest value is 5 (of a), minimum window so far is 6 (0 to 5) First pass is done Take next character. F is not part of hash table, skip it Next character (c), update hash table hc = 7 Find new window, smallest value is 3 (of b) and highest value is 7 (of c) New window is 3 to 7 => 5 Keep on doing it till last character of string X I hope its clear now Edit There are some concerns about finding max and min value from hash We can maintain sorted Link-list and map it with hash table Whenever any element from Link list changes, it should be re-mapped to hash table Both these operation are O(1) Total space would be m+m.

This is how I would do it: Create a hash table for all the characters from string Y. (I assume all characters are different in Y). First pass: Start from first character of string X.

Update hash table, for exa: for key 'a' enter location (say 1). Keep on doing it until you get all characters from Y (until all key in hash table has value). If you get some character again, update its newer value and erase older one.

Once you have first pass, take smallest value from hash table and biggest value. Thats the minimum window observed so far. Now, go to next character in string X, update hash table and see if you get smaller window.

Algorithm complexity: O(n) : One pass space: O(k) Edit: Lets take an example here: String x = "coobdafceeaxab" String y = "abc" First initialize a hash table from characters of Y. Ha = -1 hb = -1 hc = -1 Now, Start from first character of X. First character is c, hc = 0 Second character (o) is not part of hash, skip it... Fourth character (b), hb = 3 .. Sixth character(a), enter hash table ha = 5.

Now, all keys from hash table has some value. Smallest value is 0 (of c) and highest value is 5 (of a), minimum window so far is 6 (0 to 5). First pass is done.

Take next character. F is not part of hash table, skip it. Next character (c), update hash table hc = 7.

Find new window, smallest value is 3 (of b) and highest value is 7 (of c). New window is 3 to 7 => 5. Keep on doing it till last character of string X.

I hope its clear now. Edit There are some concerns about finding max and min value from hash. We can maintain sorted Link-list and map it with hash table.

Whenever any element from Link list changes, it should be re-mapped to hash table. Both these operation are O(1) Total space would be m+m.

I don't actually understand what you are describing. Can you take my example above and illustrate how your arrive at the correct answer? – grokus Aug 29 '10 at 2:34 @Jack, +1 for you, however I must say each time you look up min and max values in your hash, it takes O(m), so your overall complexity is O(nm), not O(n) as you advertised.

– grokus Aug 29 '10 at 20:30 Well, there is a way you can maintain ordered list where you can keep track of first and last occurrence and map it to hash. Whenever you change key/value, update its value in list using hash. This is O(1) due to hash.

– Jack Aug 30 '10 at 6:21 Maintain Link list and map with hash. Total complexity will be O(n), space will be m + m. – Jack Aug 30 '10 at 10:12 Check out my answer for implementations in Java and C++ of this method.

– Sheldon L. Cooper 21 Mai0 at 16:31.

This is my solution in C++, just for reference. Update: originally I used std::set, now I change it to tr1::unordered_map to cut complexity down to n^2, otherwise these two implementations look pretty similar, to prevent this post from getting too long, I only list the improved solution. #include #include #include using namespace std; using namespace std::tr1; typedef tr1::unordered_map hash_t; // Returns min substring width in which sentence contains all chars in word // Returns sentence's length + 1 if not found size_t get_min_width(const string &sent, const string &word) { size_t min_size = sent.size() + 1; hash_t char_set; // char set that word contains for (size_t I = 0; I Insert(hash_t::value_type(wordi, 1)); } for (size_t I = 0; I.

1 I think you should put your reference solution in the question, not as an answer. – Albin Sunnanbo Aug 28 '10 at 19:53 Well, it is maybe the answer – ring0 Aug 28 '10 at 20:00.

Here's my solution in C++: int min_width(const string& x, const set& y) { vector at; for (int I = 0; I 0) at. Push_back(i); int ret = x.size(); int start = 0; map count; for (int end = 0; end 1) countxatstart++--; if (count.size() == y.size() && ret > atend - atstart + 1) ret = atend - atstart + 1; } return ret; } Edit: Here's an implementation of Jack's idea. It's the same time complexity as mine, but without the inner loop that confuses you.Int min_width(const string& x, const set& y) { int ret = x.size(); map index; set index_set; for (int j = 0; j 0) { if (index.

Count(xj) > 0) index_set. Erase(indexxj); index_set. Insert(j); indexxj = j; if (index.size() == y.size()) { int I = *index_set.begin(); if (ret > j-i+1) ret = j-i+1; } } } return ret; } In Java it can be implemented nicely with LinkedHashMap: static int minWidth(String x, HashSet y) { int ret = x.length(); Map index = new LinkedHashMap(); for (int j = 0; j j - I + 1) ret = j - I + 1; } } } return ret; } All operations inside the loop take constant time (assuming hashed elements disperse properly).

The time complexity is linear in the size of the string "x" (assuming a constant size alphabet. ) This implementation assumes there's always a solution. – Sheldon L.

Cooper Aug 28 '10 at 20:30 @Sheldon, I tested your code and it does produce correct result, however you have a while loop inside a for loop, so the complexity looks to be O(n^2) to me. – grokus Aug 29 '10 at 2:49 No, it's O(n). The while loop executes at most n iterations OVERALL, since "start" is incremented at each iteration.

– Sheldon L. Cooper Aug 29 '10 at 4:59 In other words, you're claiming that the code works but the while loop iterates more than n times overall. Which implies that the variable "start" would have a value greater than n.

Then, the vector "at" is accessed outside its boundaries. Hence, the code is broken. Contradiction, that comes from assuming that the while loop iterates more than n times overall.

– Sheldon L. Cooper Aug 29 '10 at 5:35 Only looking at the first loop, this code is already O(n log m). – Nabb Aug 29 '10 at 7:19.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.