[C++] Beginner friendly binary search
Intuition\nUse binary search template to find a minimal window that can be ignored in t.\n\n# Approach\nGiven a window size:\n0. we need to match t.size() - win
# Intuition\nUse binary search template to find a minimal window that can be ignored in `t`.\n\n# Approach\nGiven a window size:\n0. we need to match `t.size() - window` char.\n1. greedy match `t` from `s`\'s left to right, keep matched one in an array\n2. greedy match `t` from `s`\'s right to left by a window until all char in `t` are matched.\n\n# Complexity\n- Time complexity:\nO(NlogN)\n- Space complexity:\nO(N)\n\n# Code\n```\nclass Solution {\npublic:\n    bool criteria(string& s, string& t, int window) {\n        // should match t.size() - window\n        int n = t.size() - window;\n        if (n == 0) return true;\n        vector<int> collection(n, -1);\n        int index = 0;\n        int collectionIdx = 0;\n        int validCnt = 0;\n        for (int i = 0; i < s.size(); ++i) {\n            if (s[i] == t[index] && collectionIdx < collection.size()) {\n                collection[collectionIdx] = i;\n                collectionIdx++;\n                validCnt++;\n                index++;\n            }\n        }\n        if (validCnt == n) return true;\n        \n        index = t.size() - 1;\n        collectionIdx = n - 1;\n        for (int i = s.size() - 1; i >= 0; --i) {\n            if (s[i] == t[index] && collectionIdx >= 0) {\n                \n                if (collection[collectionIdx] == -1) {\n                    validCnt++;\n                }\n                collection[collectionIdx] = i;\n                if (validCnt == n) {\n                    if (collectionIdx == 0) return true;\n                    if (collectionIdx > 0 && i > collection[collectionIdx - 1]) return true;\n                }\n                index--;\n                collectionIdx--;\n            }\n        }\n        return false;\n        \n    }\n    int minimumScore(string s, string t) {\n        int left = 0;\n        int right = t.size();\n        \n        while (left < right) {\n\n            int mid = left + (right - left) / 2;\n            if (criteria(s, t, mid)) right = mid;\n            else left = mid + 1;\n        }\n        return left;\n    }\n};\n```
['C++']