Find prefix and suffix and check the smallest removal score
\n### Fact\n> only the leftmost non-removal and rightmost non-removal positions affect the score, so we just need to find prefix and suffix.\n\n\nWe have to loo
\n### Fact\n> only the leftmost non-removal and rightmost non-removal positions affect the score, so we just need to find prefix and suffix.\n\n\nWe have to look for all [prefix, suffix] pairs to get the most optimized score.\n\n\n## Solution\n\n```\nclass Solution {\npublic:\n    int minimumScore(string s, string t) {\n        int m = s.size(), n = t.size();\\\n        // get rightmost index in s that all t\'s suffix sequence can be constructed\n        vector<int> suffix(n, -1);\n        int k = n - 1;\n        for (int i = m - 1; i >= 0 && k >= 0; --i) {\n            if (s[i] == t[k]) {\n                suffix[k--] = i;\n            }\n        }\n        // t can be formed by char sequence in s, no removal needed\n        if (k < 0) {\n            return 0;\n        }\n        \n        // t[0...k] should be removed\n        int minScore = k + 1;\n        \n        // get leftmost index in s that all t\'s prefix sequence can be constructed\n        vector<int> prefix(n, -1);\n        k = 0;\n        for (int i = 0; i < m && k < n; ++i) {\n            if (s[i] == t[k]) {\n                prefix[k++] = i;\n            }\n        }\n\n        // t can be formed by char sequence in s, no removal needed\n        if (k >= n) {\n            return 0;\n        }\n        // t[k...n-1] shoule be removed\n        minScore = min(minScore, n - k);\n        \n\n        // now, we check if there exist prefix and suffix \n        // t[...i] and t[j...] to get the smaller score with  j - 1 - (i + 1) + 1\n        for (int i = 0; i < n; i++) {\n            // now, there exist prefix t[...i]\n            if (prefix[i] != -1) {\n                // s[0...leftMost]\n                int leftMost = prefix[i];\n                \n                // find suffix t[j...]\n                int j = n - 1;\n                while(j >= 0 && suffix[j] > leftMost) {\n                    j--;\n                }\n                // j is -1 or suffix[j] <= leftMost\n                // j is -1 means all chars t[0..n-1] can be removed \n                if (j == -1) {\n                    minScore = min(minScore, n - 1 + 1);\n                } else {\n                    // now, we can know t[...i]  .... t[j + 1 ...]\n                    int score = j - (i + 1) + 1;\n                    minScore = min(minScore, score);\n                }\n            }\n        }\n        \n        return minScore;\n    }\n};\n\n```
['C++']