import java.util.*;
class Subsequence2Pointer {

    public static int numOfGoodIndices(String a, String b) {

        int n = a.length();
        int m = b.length();

        // If b has only one character,
        // removing it leaves empty string,
        // which is always a subsequence.
        if (m == 1) {
            return 1;
        }

        int[] left = new int[m];
        int[] right = new int[m];

        Arrays.fill(left, -1);
        Arrays.fill(right, -1);

        // Build left[]
        // left[i] = earliest position in a
        // where b[0...i] can be matched.
        int j = 0;

        for (int i = 0; i < n && j < m; i++) {
            if (a.charAt(i) == b.charAt(j)) {
                left[j] = i;
                j++;
            }
        }

        // Build right[]
        // right[i] = latest position in a
        // where b[i...m-1] can be matched.
        j = m - 1;

        for (int i = n - 1; i >= 0 && j >= 0; i--) {
            if (a.charAt(i) == b.charAt(j)) {
                right[j] = i;
                j--;
            }
        }

        // if an index is supposed to be good then left[i-1] < right[i+1]
        // meaning index i-1 in b was found at left[i-1] and occurs before right[i+1] occurance 
        // 

        int good = 0;

        for (int i = 0; i < m; i++) {
        	int l = (i == 0) ? -1 : left[i - 1];
        	int r = (i == m - 1) ? n : right[i + 1];
        	boolean prefixOk = (i == 0) || (l != -1);
        	boolean suffixOk = (i == m - 1) || (r != -1);
        	if (prefixOk && suffixOk && l < r) {
        		good++;
        	}
        }

        return good;
    }

    public static void main(String[] args) {
        //"If b itself is already a subsequence of a, then removing any character from b should still give a subsequence."
        // if not subsequence then IFF we have one char somewhere that needs to be removed then thats the ans.. 
        // so either ans is 1 or length of string or 0 if not possible at all
        String a = "abxcdyef";
        String b = "abcde";

        System.out.println(numOfGoodIndices(a, b));
        System.out.println(numOfGoodIndices("abc", "xy"));
        System.out.println(numOfGoodIndices("abcd", "ayd"));
    }
}