Greedy | Largest Prefix and suffix | 11ms
Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n\nclass Solution {\n  public int minimumScore(String s, String t) {\n    int[] grea
# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\n  public int minimumScore(String s, String t) {\n    int[] greatestUnmatchedLeft = new int[s.length()];\n\n    int minScore = t.length();\n    for (int i = 0; i < s.length(); i++) {\n      if (i > 0 && greatestUnmatchedLeft[i - 1] == t.length()) {\n        return 0;\n      }\n\n      greatestUnmatchedLeft[i] = (i > 0 ? greatestUnmatchedLeft[i - 1] : 0)\n          + (s.charAt(i) == t.charAt(i > 0 ? greatestUnmatchedLeft[i - 1] : 0) ? 1 : 0);\n    }\n\n    if (greatestUnmatchedLeft[s.length() - 1] == t.length()) {\n      return 0;\n    }\n\n    int smallestUnmatchedRight = t.length() - 1;\n    minScore = Math.min(minScore, t.length() - greatestUnmatchedLeft[s.length() - 1]);\n    for (int j = s.length() - 1; j >= 0; j--) {\n      if (s.charAt(j) == t.charAt(smallestUnmatchedRight)) {\n        smallestUnmatchedRight--;\n        if (smallestUnmatchedRight < 0) {\n          return 0;\n        }\n      }\n\n      if (j > 0 && greatestUnmatchedLeft[j - 1] > smallestUnmatchedRight) {\n        return 0;\n      }\n\n      minScore = Math.min(minScore, smallestUnmatchedRight - (j > 0 ? greatestUnmatchedLeft[j - 1] : 0) + 1);\n    }\n\n    return minScore;\n  }\n}\n```
['Array', 'Greedy', 'Java']