Beginner Friendly | Simple Java code | Beats 100%
Intuition\nTo solve the problem of counting valid substrings in word1 that can form word2, we need to:\n\n1. Understand Character Counting: Check if substrings 
# Intuition\nTo solve the problem of counting valid substrings in word1 that can form word2, we need to:\n\n1. Understand Character Counting: Check if substrings of word1 can contain all characters of word2 in required frequencies.\n2. Optimize for Efficient Searching: Use a sliding window technique to efficiently find and count valid substrings.\n# Approach\n## Overview\n1. Character Counting: Maintain counts of characters in both word1 and word2 to determine if a substring is valid.\n2. Sliding Window Technique: Use two pointers to define the current window in word1 and check for validity against word2.\n## Detailed Steps\n1. Initialize Character Counts:\n\n- Create a targetCount HashMap to store character frequencies of word2.\n- Initialize a windowCount HashMap to track character frequencies in the current window of word1.\n2. Setup the Sliding Window:\n\n- Use two pointers (left and right) to represent the current window in word1.\n- Expand the window by moving the right pointer and include characters in windowCount.\n3. Check for Validity:\n\n- If the current window contains all characters from word2 in required frequencies, count valid substrings and then try to contract the window from the left.\n4. Count Valid Substrings:\n\n- For each valid window, add the number of valid substrings that can be formed from the current right pointer position to the end of word1.\n5. Return the Result:\n\n- Return the total count of valid substrings.\n\n# Complexity Analysis\n## Time Complexity: \n- $$O(N)$$, where N is the length of word1. Each character is processed at most twice (once by the right pointer and once by the left pointer).\n## Space Complexity:\n- $$O(K)$$, where K is the number of unique characters in word1 and word2, since we maintain character counts in two hash maps.\n\n# Code\n```java []\nimport java.util.HashMap;\n\nclass Solution {\n    public long validSubstringCount(String word1, String word2) {\n        int n = word1.length();\n        int m = word2.length();\n        if (n < m) return 0;\n\n        HashMap<Character, Integer> targetCount = new HashMap<>();\n        for (char c : word2.toCharArray()) {\n            targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);\n        }\n\n        long validCount = 0;\n        HashMap<Character, Integer> windowCount = new HashMap<>();\n        int left = 0;\n\n        for (int right = 0; right < n; right++) {\n\n            windowCount.put(word1.charAt(right), windowCount.getOrDefault(word1.charAt(right), 0) + 1);\n\n            while (isValid(windowCount, targetCount)) {\n                validCount += (n - right); \n                windowCount.put(word1.charAt(left), windowCount.get(word1.charAt(left)) - 1);\n                if (windowCount.get(word1.charAt(left)) == 0) {\n                    windowCount.remove(word1.charAt(left));\n                }\n                left++;\n            }\n        }\n\n        return validCount;\n    }\n\n    private boolean isValid(HashMap<Character, Integer> windowCount, HashMap<Character, Integer> targetCount) {\n        for (char c : targetCount.keySet()) {\n            if (windowCount.getOrDefault(c, 0) < targetCount.get(c)) {\n                return false;\n            }\n        }\n        return true;\n    }\n}\n\n```
['Java']