Step-By-Step Explanation
The very bruteforce way to solve this problem is, we have the words of string. So, what we gonna do we iterate over the String s & if we find the subsequences (
The very **`bruteforce`** way to solve this problem is, we have the words of string. So, what we gonna do we iterate over the **String s** & if we find the subsequences *(appearing of those characters in word string)* then we gonna increment our count, otherwise if they are not present ignore them & carry on.\n\nLet\'s look at the code, \n\n```\nclass Solution {\n    public int numMatchingSubseq(String s, String[] words) {\n        int index = -1;\n        int count = 0;\n        boolean notSubSeq = true;\n        \n        for(String word : words) {\n            for(char c : word.toCharArray()) {\n                index = s.indexOf(c, index + 1);\n                if (index == -1) {\n                    notSubSeq = false;\n                    break;\n                }\n            }\n            if(notSubSeq)\n                count++;\n            notSubSeq = true;\n            index = -1;\n        }\n        return count;\n    }\n}\n```\nANALYSIS :-\n\nThe **time complexity** is going to be `O(words.length * (S.length + words[i].length)`, **space complexity** is `O(max(words[i].length)`. Please correct me if I am wrong.\n\n<hr>\n<hr>\n\n**Now, let\'s optimise it**\n\n<hr>\n<hr>\n\nOkay, so what you can think of is to create a map and store those **string s** characters along with **words[]** starting with those characters.\nLet\'s take an example and understand it visually,\n\n```\nInput: s = "abcde", words = ["a","bb","acd","ace"]\nOutput: 3\n```\n\n![image](https://assets.leetcode.com/users/images/65bf478f-fb1d-48f0-a806-e30d4231ed4f_1658283658.6039329.png)\n\n**`So, now first of all I\'ll gonna add all the words present in my array starting with characters a`**\n\n![image](https://assets.leetcode.com/users/images/6f97efba-4cd4-4d46-a8e0-eb6d8abbe3b9_1658283819.484303.png)\n\n**`Next we have b characters to add`**\n\n![image](https://assets.leetcode.com/users/images/bd6c982e-0370-4848-8f06-cf990ba5c092_1658283916.11681.png)\n\nNow, what we\'ll do is iterate over all the characters present in our super-string **s** and remove their occurence from the map of that character.\n* So, intially we have **a** we gonna remove all the characters of **a** present in our word list and if any word becomes empty string we gonna increment our count\n![image](https://assets.leetcode.com/users/images/ee5f8dee-6637-4588-9935-870531a7a595_1658284216.6068559.png)\n\n* As, you can see as well we have **"a"** in our word dataset as well & our `count is 1`\n\n\n* So now what we do with remaining word present in front of **a** is delete from their and put them correspond to their characters & then what we gonna do is start our entry from next character in string i.e. **b** and remove all the characters present in our word array\n![image](https://assets.leetcode.com/users/images/8a93142f-93fb-419e-afe9-31cd2c2c8705_1658284704.813729.png)\n\n* So now what we do with remaining word present in front of **b** is delete from their and put them correspond to their characters, but none of the word become empty string so, we won\'t increment our count.\n* Start our entry from next character in string i.e. **c** and remove all the characters present in our word array\n![image](https://assets.leetcode.com/users/images/821b7513-a2ac-4b13-97a0-6aed8295f5c8_1658284955.322419.png)\n\n* Now what we do with remaining word present in front of **c** is delete from their and put them correspond to their characters, but none of the word become empty string so, we won\'t increment our count.\n* Start our entry from next character in string i.e. **d** and remove all the characters present in our word array\n![image](https://assets.leetcode.com/users/images/829cb839-c111-4c38-bdb2-8bb7fef9ea92_1658285143.0286496.png)\n\n* As, our **d** character array wordlist becomes empty by removing the character from the string, so we gonna increment our `count = 2`\n* Start our entry from next character in string i.e. **e** and remove all the characters present in our word array\n![image](https://assets.leetcode.com/users/images/614e8207-fd30-418a-aa77-6ea4dcc94e58_1658285336.1940873.png)\n\n* As, our **e** character array wordlist becomes empty by removing the character from the string, so we gonna increment our `count = 3`\n* And as you can see in the word there only is 3 word subsequences which are possible and our answer is 3 as well\n```\nwords = ["a","acd","ace"]\nOutput: 3\n```\n\nNow, I hope ladies and gentlemen you got the idea, what we are doing is!!\n\nLet\'s code it up then,\n\n```\nclass Solution {\n    public int numMatchingSubseq(String s, String[] words) {\n        Map<Character, Queue<String>> map = new HashMap<>();\n        int count = 0;\n\n        for(int i = 0; i < s.length(); i++) {\n            map.putIfAbsent(s.charAt(i), new LinkedList<>());\n        }\n        \n        for(String word : words) {\n            char startingChar = word.charAt(0);\n            if(map.containsKey(startingChar)) {\n                map.get(startingChar).offer(word);\n            }\n        }\n        for(int i = 0; i < s.length(); i++) {\n            char startingChar = s.charAt(i);\n            Queue<String> q = map.get(startingChar);\n            int size = q.size();\n            for(int k = 0; k < size; k++) {\n                String str = q.poll();\n                if(str.substring(1).length() == 0) {\n                    count++;\n                } else {\n                    if(map.containsKey(str.charAt(1))) {\n                        map.get(str.charAt(1)).add(str.substring(1));\n                    }\n                }\n            }\n        }\n        return count;\n    }\n}\n```
[]