Count Substrings That Can Be Rearranged to Contain a String I

• Pre-calculate the character frequency map of word2, let's call it freq2.
• Initialize a counter for valid substrings, count, to 0.
• Use nested loops to generate all substrings of word1. The outer loop iterates through the starting index i from 0 to n-1, and the inner loop iterates through the ending index j from i to n-1.
• For each substring word1[i...j], maintain a running character frequency map, currentFreq.
• After adding word1.charAt(j) to the window, check if currentFreq has at least as many of each character as freq2.
• If the condition is met, it means the substring word1[i...j] is valid, so increment the count.
• After iterating through all substrings, return the total count.

The brute-force method systematically checks every substring. We can optimize the process slightly by not re-calculating the frequency map for each substring from scratch. For a fixed starting point i, as we extend the substring by incrementing the end point j, we can update the frequency map of the current substring in O(1) time. Then, for each new substring word1[i...j], we perform a check against the frequency map of word2.

1class Solution {2    public long countSubstrings(String word1, String word2) {3        int n = word1.length();4        int m = word2.length();5        long count = 0;6 7        int[] freq2 = new int[26];8        for (char c : word2.toCharArray()) {9            freq2[c - 'a']++;10        }11 12        for (int i = 0; i < n; i++) {13            int[] currentFreq = new int[26];14            for (int j = i; j < n; j++) {15                currentFreq[word1.charAt(j) - 'a']++;16                if (isSufficient(currentFreq, freq2)) {17                    count++;18                }19            }20        }21        return count;22    }23 24    private boolean isSufficient(int[] freq1, int[] freq2) {25        for (int i = 0; i < 26; i++) {26            if (freq1[i] < freq2[i]) {27                return false;28            }29        }30        return true;31    }32}

• First, compute the character frequency map for word2, let's call it freq2.
• Initialize two pointers, left = 0 and right = 0, to represent the current window word1[left...right-1].
• Initialize a frequency map for the window, windowFreq, and a total count of valid substrings, count = 0.
• Iterate with the left pointer from 0 to n-1.
• For each left, expand the window by advancing the right pointer until the window word1[left...right-1] becomes valid (i.e., its character counts are sufficient).
• Once a valid window word1[left...right-1] is found, we know that any substring starting at left and ending at right-1 or later is also valid. The number of such substrings is n - (right - 1). Add this to count.
• After processing left, shrink the window by decrementing the count of word1.charAt(left) and advancing left to the next position.
• The right pointer does not reset, which is key to the algorithm's efficiency.
• Return the total count.

We use two pointers, left and right, to maintain a window over word1. The left pointer iterates through all possible starting positions of a substring. For each left, we expand the window by moving right forward until the substring word1[left...right-1] contains enough characters to satisfy the requirements of word2. Once this minimal valid window is found, we know that this window, and any window starting at left that extends beyond right-1, are all valid. The number of such valid substrings is n - (right - 1). We add this to our total count. Then, we slide the window forward by incrementing left and removing word1.charAt(left) from our window's frequency count. The right pointer continues from where it was, ensuring that each character in word1 is visited by left and right at most once.

1class Solution {2    public long countSubstrings(String word1, String word2) {3        int n = word1.length();4        int m = word2.length();5        long count = 0;6 7        int[] freq2 = new int[26];8        for (char c : word2.toCharArray()) {9            freq2[c - 'a']++;10        }11 12        int[] windowFreq = new int[26];13        int right = 0;14        for (int left = 0; left < n; left++) {15            // Expand the window by moving 'right' until the substring is valid16            while (right < n && !isSufficient(windowFreq, freq2)) {17                windowFreq[word1.charAt(right) - 'a']++;18                right++;19            }20 21            // If the window is valid, all substrings starting at 'left' and ending at 'right-1' or later are valid.22            if (isSufficient(windowFreq, freq2)) {23                count += (long)n - (right - 1);24            }25 26            // Shrink the window from the left for the next iteration27            windowFreq[word1.charAt(left) - 'a']--;28        }29        return count;30    }31 32    private boolean isSufficient(int[] freq1, int[] freq2) {33        for (int i = 0; i < 26; i++) {34            if (freq1[i] < freq2[i]) {35                return false;36            }37        }38        return true;39    }40}