Java Prefix+Suffix array
Intuition\n Describe your first thoughts on how to solve this problem. \nTry to delete every possible window of size \'k\'. If we are able to delete window of s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry to delete every possible window of size \'k\'. If we are able to delete window of size \'k\', then try to find a better minimum answer.\n\nLet\'s say the window is i......j. Now check if prefix[0...i-1] and suffix[j+1...t.length()-1] are non-overlapping.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\nO(n*logn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\n    public int minimumScore(String s, String t) {\n\n        int n=t.length();\n\n\n        // prefix[i] is the min index in string \'s\' such that prefix[i] of string \'t\' is a subsequence of string \'s\'\n        // suffix[i] is the min index in string \'s\' such that suffix[i] of string \'t\' is a subsequence of string \'s\'\n        int[] prefix = new int[n];\n        int[] suffix = new int[n];\n        Arrays.fill(prefix, Integer.MAX_VALUE);\n        Arrays.fill(suffix, -1);\n        int j=0;\n        for(int i=0;i<s.length();++i)\n        {\n            if(j<t.length() && s.charAt(i)==t.charAt(j))\n            {\n                prefix[j] = i; \n                j++;\n            }\n        }   \n        j=t.length()-1;\n        for(int i=s.length()-1;i>=0;--i)\n        {\n            if(j>=0 && s.charAt(i)==t.charAt(j))\n            {\n                suffix[j] = i; \n                j--;\n            }\n        }   \n        \n        int low=0, high=n;\n        int ans=n;\n        while(low<=high)\n        {\n            int mid=low+(high-low)/2;\n            if(poss(s, t, mid, prefix, suffix))\n            {\n                ans=mid;\n                high=mid-1;\n            }\n            else\n                low=mid+1;\n        }\n        return ans;\n        \n    }\n    public boolean poss(String s, String t, int k, int[] prefix, int[] suffix)\n    {\n        int start=0, end=k-1;\n        int n=t.length();\n\n        if(k>n)\n            return true;\n\n        while(end<n)\n        {\n            // t[0....start-1] and t[end+1.......n-1]\n            if(start==0 && end<n-1 && suffix[end+1] != -1)\n                return true;\n            if(start>0 && end==n-1 && prefix[start-1] != Integer.MAX_VALUE)\n                return true;\n            if(start>0 && end<n-1 && prefix[start-1] < suffix[end+1])\n                return true; \n            start++;\n            end++;\n        }\n        return false;\n    }\n}\n```
['Java']