【C++ || Java || Python3】 Binary search in value range
I know almost nothing about English, pointing out the mistakes in my article would be much appreciated.\n\n> In addition, I\'m too weak, please be critical of m
> **I know almost nothing about English, pointing out the mistakes in my article would be much appreciated.**\n\n> **In addition, I\'m too weak, please be critical of my ideas.**\n---\n\n# Intuition\n1. **Clearly, "remove all" is no worse than "remove some" for selected subsequences.**\n2. Furthermore, if deleting a short string can make $t$ a subsequence of $s$, then it must also be true to expand on the basis of this short string.\n3. Therefore, the answer is dichotomous in the value domain, and binary search can be considered.\n4. In each sample, check whether each substring of length $x$ meets the requirements after deletion. If any one is found, the result of $x$ is true, otherwise it is false.\n5. Note that when enumerating each substring, $t$ will be cut into two segments, so it is only necessary to check whether the $left + right$ is a subsequence of $s$.\n6. For the left part, greedily match the left side of $s$, and record $t[0...i]$ that can become the smallest $j$ of a subsequence of $s[0...j]$. The same is true for the right part, the record $t[i...n]$ can become the largest $j$ of the subsequence of $s[j...m]$.\n7. In this way, it is enough to scan one round and check whether there is a qualified substring.\n\n# Approach\n1. \n\n# Complexity\n- Time complexity: $O(m + n\\log{n})$\n- Space complexity: $O(m+n)$\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int m = s.size(), n = t.size();\n        vector<int> left(n+2, -1), right(n+2, m);\n        int p = 0;\n        for (int i = 0; i < n; ++i) {\n            while (p < m && s[p] != t[i]) p++;\n            left[i+1] = p++;\n        }\n        p = m - 1;\n        for (int i = n - 1; i >= 0; --i) {\n            while (p >= 0 && s[p] != t[i]) p--;\n            right[i+1] = p--;\n        }\n        auto check = [&](int x) -> bool {\n            for (int i = 0; i + x - 1 < n; ++i) {\n                if (left[i] < right[i+x+1]) \n                    return true;\n            }\n            return false;\n        };\n        int l = 0, r = n;\n        while (l <= r) {\n            int x = (l + r) / 2;\n            if (check(x)) r = x - 1;\n            else l = x + 1;\n        }\n        return l;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int minimumScore(String s, String t) {\n        int m = s.length(), n = t.length();\n        int []left = new int[n+2];\n        int []right = new int[n+2];\n        int p = 0;\n        for (int i = 0; i < n; ++i) {\n            while (p < m && s.charAt(p) != t.charAt(i)) p++;\n            left[i+1] = p++;\n        }\n        left[0] = -1;\n        p = m - 1;\n        for (int i = n - 1; i >= 0; --i) {\n            while (p >= 0 && s.charAt(p) != t.charAt(i)) p--;\n            right[i+1] = p--;\n        }\n        right[n+1] = m;\n\n        int l = 0, r = n;\n        while (l <= r) {\n            int x = (l + r) / 2;\n            boolean flag = false;\n            for (int i = 0; i + x - 1 < n; ++i) {\n                if (left[i] < right[i+x+1]) \n                    flag = true;\n            }\n            if (flag) r = x - 1;\n            else l = x + 1;\n        }\n        return l;\n    }\n}\n```\n``` Python3 []\nclass Solution:\n    def minimumScore(self, s: str, t: str) -> int:\n        m, n = len(s), len(t)\n        left, right = [-1] * (n+2), [m] * (n+2)\n        p = 0\n        for i in range(n):\n            while p < m and s[p] != t[i]: p += 1\n            left[i+1] = p\n            p += 1\n        p = m - 1\n        for i in range(n-1, -1, -1):\n            while p >= 0 and s[p] != t[i]: p -= 1\n            right[i+1] = p\n            p -= 1\n\n        def check(x): \n            for i in range(n + 1 - x):\n                if left[i] < right[i+x+1]:\n                    return True\n            return False\n\n        l, r = 0, n\n        while l <= r:\n            x = (l + r) // 2;\n            if (check(x)): r = x - 1\n            else: l = x + 1\n        return l\n```
['Binary Search', 'Greedy', 'C++', 'Java', 'Python3']