C++ 5 lines solution. But why the question mentioned "t is very long" and "binary search"?

  • 1

    Iterate through t and check if can find chars in s in order.

     bool isSubsequence(string s, string t) {
            if (s.empty()) { return true; }
            for (int j = 0, i = 0; j < t.length(); j++) {
                if (s[i] == t[j] && ++i == s.length()) { return true; }
            return false;

    However, this is a O(m + n) solution and didn't care about the constraint that "t is potentially a very long (length ~= 500,000) string". The question tag also mentioned "binary search".
    Can someone explain how to make use of these constraints/hints?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.