Sliding window | Java | O(n * 26)
Approach\nSliding window approch.\n\n# Complexity\n- Time complexity:\nO(n*26) \nn -> length of word1\n\n- Space complexity:\nO(26)\n\n# Code\njava []\nclass So
# Approach\nSliding window approch.\n\n# Complexity\n- Time complexity:\nO(n*26) \nn -> length of word1\n\n- Space complexity:\nO(26)\n\n# Code\n```java []\nclass Solution {\n    public long validSubstringCount(String word1, String word2) {\n        long res = 0;\n        int[] ct1 = new int[26], ct2 = new int[26];\n        int len1 = word1.length(), len2 = word2.length(), st = 0;\n        if(len2 > len1) return 0;\n\n        for(int i=0; i<len2; i++){\n            ct2[word2.charAt(i) - \'a\']++;\n        }\n\n        for(int i=0;i<len2-1;i++){\n            ct1[word1.charAt(i) - \'a\']++;\n        }\n\n        for(int j=len2-1;j<len1;j++){\n            ct1[word1.charAt(j) - \'a\']++;\n\n            if(hasPrefix(ct1, ct2)){\n                int k = 0, idx = word1.charAt(st) - \'a\';\n                while(ct1[idx] >= ct2[idx] && (j-st+1) >= len2){\n                    k++;\n                    st++;\n                    ct1[idx]--;\n\n                    if(ct1[idx]<ct2[idx])\n                        break;\n\n                    idx = word1.charAt(st) - \'a\';\n                }\n                res += (len1 - j) * k;\n            }\n\n        }\n\n        return res;\n    }\n    \n    boolean hasPrefix(int[] ct1, int[] ct2){\n        for(int i=0;i<26;i++){\n            if(ct1[i] < ct2[i])\n                return false;\n        }\n        return true;\n    }\n}\n\n// cccbaaa, abc\n// 9\n```
['Hash Table', 'Two Pointers', 'String', 'Sliding Window', 'Java']