C++ linear scan O(n) beats 100%
We want a prefix of t and a suffix of t such that when we concatenate them, it is a valid subsequence of s.\n\nclass Solution {\npublic:\n  int minimumScore(str
We want a prefix of `t` and a suffix of `t` such that when we concatenate them, it is a valid subsequence of `s`.\n```\nclass Solution {\npublic:\n  int minimumScore(string s, string t) {\n    int left = 0, right = t.size() - 1;\n    \n    // Will contain the final answer.\n    int ans = t.size();\n    \n    // All the indices where the left prefix matched s from the left side.\n    vector<int> leftMatches;\n    for (int i = 0; i < s.size(); ++i) {\n      if (left < t.size() && s[i] == t[left]) {\n        // The length of leftMatches always == left.\n        leftMatches.push_back(i);\n        ++left;\n      }\n    }\n    \n    ans = min(ans, 1 + right - left);\n    \n    // Start matching suffixes of t with s starting from the right side.\n    for (int i = s.size() - 1; i >= 0; --i) {\n      if (right >= 0 && s[i] == t[right]) {\n        --right;\n        \n        // Pop the rightmost index from leftMatches by decrementing left\n        // if we are now behind it.\n        while ((left - 1) >= 0 && i <= leftMatches[left - 1]) {\n          --left;\n        }\n        \n        if (right < left) {\n          // Entire t is a subsequence of s.\n          return 0;\n        }\n\n        ans = min(ans, 1 + right - left);\n      }\n    }\n    return ans;\n  }\n};\n```
[]