This is actually the best answer.
I've been asked a similar question named "last byte" in an interview, I showed them the high voted answer(scan left to right, check i == n1 or not), but they said it could still be faster by scanning reverse way.
I'm not clear at that time, until I saw this answer. Indeed this one being the optimal solution.
JadenPan
@JadenPan
Posts made by JadenPan

RE: JAVA, check only the end of array

RE: C++, DP with explanation, O(ST) 53ms
Similar idea, but I start thinking by the substring ending index, so it would be kind of redundant at return statement, and I use INT_MAX as sentinel instead of 1.
string minWindow(string S, string T) { int m = S.size(), n = T.size(), res = INT_MAX, tail; vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX)); for(int i = 0; i <= m; i++) dp[i][0] = 0; for(int i = 1; i <= m; i++){ for(int j = 1; j <= i && j <= n; ++j){ if(S[i1] != T[j1]) dp[i][j] = dp[i1][j] == INT_MAX? INT_MAX : dp[i1][j]+1; else{ dp[i][j] = min(dp[i1][j1], dp[i1][j]); if(dp[i][j] != INT_MAX) dp[i][j]++; } }// for j }// for i for(int i = m; i >= 0; i){ if(dp[i][n] <= res){ res = dp[i][n]; tail = i; } } return res == INT_MAX ? "" : S.substr(tail  res, res); }

RE: Why my dp solution get memory exceed limit error?
In C++, vector do cost more space than an int array.
For this problem, to handle MLE, you can use the strategy called "rolling array".
Since for the dp formula, dp[i][j] only need the information of dp[i1][j1], so you can always use an extra tmp var to store it and update in the fly.
My code here:int findLength(vector<int>& A, vector<int>& B) { int m = A.size(), n = B.size(), ans = 0, tmp = 0, cur; vector<int> dp(n+1, 0); for(int i = 1; i <= m; ++i){ tmp = 0; for(int j = 1; j <= n; ++j){ cur = dp[j]; if(A[i1] == B[j1]) dp[j] = 1 + tmp; else dp[j] = 0; tmp = cur; ans = max(ans, dp[j]); } } return ans; }

RE: anybody came up with the O(n) time and O(k) space solution?
@awice Thank you, nice proof by contradiction.

RE: Accepted DFS C++ Solution
@bigoffer4all I got a rough idea, but how dose the prime numbers like 19,31,73 come out? Any strategies on choosing these numbers?

RE: Accepted DFS C++ Solution
Could you please give some explanation on your hashing function? It's kind of abstract. Thank you!

RE: c++, map based short solution
@storypku Than you so much for pointing that out! I've updated my post.

c++, map based short solution
The running time complexity should be O(n²), since the bottleneck is given by finding the maxHeight in certain range.
Idea is simple, we use a map, andmap[i] = h
means, fromi
to next adjacent xcoordinate, inside this range, the height ish
.
To handle edge cases like adjacent squares, I applied STL functions, for left bound, we callupper_bound
while for right bound, we calllower_bound
.
Special thanks to @storypku for pointing out bad test cases like [[1,2],[2,3],[6,1],[3,3],[6,20]]vector<int> fallingSquares(vector<pair<int, int>>& positions) { map<int,int> mp = {{0,0}, {INT_MAX,0}}; vector<int> res; int cur = 0; for(auto &p : positions){ int l = p.first, r = p.first + p.second, h = p.second, maxH = 0; auto ptri = mp.upper_bound(l), ptrj = mp.lower_bound(r); // find range int tmp = ptrj>first == r? ptrj>second : (ptrj)++>second; // tmp will be applied by new right bound for(auto i = ptri; i != ptrj; ++i) maxH = max(maxH, i>second); // find biggest height mp.erase(++ptri, ptrj); // erase range mp[l] = h+maxH; // new left bound mp[r] = tmp; // new right bound cur = max(cur, mp[l]); res.push_back(cur); } return res; }

RE: I think this problem can not be solved in O(n) time?
@Victorcxq Yes, the randomized version, thank you for pointing that out! For O(k) space, I really can not come up with any good ideas.

anybody came up with the O(n) time and O(k) space solution?
I spend several hours on this follow up , I trie to apply heap, bucket sort, and even similar partition method like what we did on problem "top k elements", but all failed because I can not think about how we can do that with O(k) space if a hashmap used. And as long as we use something like heap the time cost will be O(nlogk).
Then I saw "Trie" in the tag, and looked for some materials, finally I found one solution online that solve this problem with trie:
http://www.geeksforgeeks.org/findthekmostfrequentwordsfromafile/
This is a heap+trie solution. But I think it's still not good enough for O(n) time O(k) space.
In this solution, the heap's size is restricted to O(k) but the trie could go very large if we have long strings. Also, though we solve it in one pass but we still need O(logk) time on each turn.
So any genius have great solutions?