Untitled

import java.util.*;

public class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        // Map to store indices of each character in s
        Map<Character, List<Integer>> charIndicesMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            charIndicesMap.computeIfAbsent(s.charAt(i), k -> new ArrayList<>()).add(i);
        }

        int count = 0;

        // Check each word in words
        for (String word : words) {
            if (isSubsequence(word, charIndicesMap)) {
                count++;
            }
        }

        return count;
    }

    private boolean isSubsequence(String word, Map<Character, List<Integer>> charIndicesMap) {
        int prevIndex = -1;

        for (char c : word.toCharArray()) {
            // If the character does not exist in s
            if (!charIndicesMap.containsKey(c)) {
                return false;
            }

            // Binary search to find the next valid position
            List<Integer> indices = charIndicesMap.get(c);
            int nextIndex = findNextIndex(indices, prevIndex);
            if (nextIndex == -1) {
                return false; // No valid position found
            }

            prevIndex = nextIndex;
        }

        return true;
    }

    private int findNextIndex(List<Integer> indices, int prevIndex) {
        // Binary search for the smallest index greater than prevIndex
        int low = 0, high = indices.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (indices.get(mid) > prevIndex) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low < indices.size() ? indices.get(low) : -1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        String s1 = "abcde";
        String[] words1 = {"a", "bb", "acd", "ace"};
        System.out.println(solution.numMatchingSubseq(s1, words1)); // Output: 3

        // Example 2
        String s2 = "dsahjpjauf";
        String[] words2 = {"ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"};
        System.out.println(solution.numMatchingSubseq(s2, words2)); // Output: 2
    }
}