Count Substrings That Can Be Rearranged to Contain a String II

• Create a frequency map targetFreq for word2.
• Initialize count = 0.
• Loop i from 0 to word1.length() - 1:
  • Create an empty frequency map currentFreq.
  • Loop j from i to word1.length() - 1:
    • Add word1.charAt(j) to currentFreq.
    • Check if currentFreq is sufficient compared to targetFreq by iterating through all 26 characters.
    • If it is, increment count.
• Return count.

First, we pre-calculate the character frequency map of word2. This map, let's call it targetFreq, will be used as the reference for our validity checks.

We then use two nested loops to generate all substrings of word1. The outer loop selects the starting index i, and the inner loop selects the ending index j.

For each starting index i, we initialize a currentFreq map for the characters. As the inner loop progresses from j = i to the end of the string, we incrementally build the substring and update currentFreq.

At each step j, we have the frequency map for the substring word1[i..j]. We then check if this substring is valid by comparing currentFreq with targetFreq. If the substring is valid, we increment a total counter. After checking all substrings, the total counter gives the final answer.

1class Solution {2    public long countSubstrings(String word1, String word2) {3        int[] targetFreq = new int[26];4        for (char c : word2.toCharArray()) {5            targetFreq[c - 'a']++;6        }7 8        long validCount = 0;9        int n = word1.length();10 11        for (int i = 0; i < n; i++) {12            int[] currentFreq = new int[26];13            for (int j = i; j < n; j++) {14                currentFreq[word1.charAt(j) - 'a']++;15                16                if (isSufficient(currentFreq, targetFreq)) {17                    // If word1[i..j] is valid, all substrings word1[i..k] where k > j are also valid.18                    // We can optimize by adding (n - j) and breaking the inner loop.19                    // But for a basic brute force, we check each one.20                    validCount++;21                }22            }23        }24        return validCount;25    }26 27    private boolean isSufficient(int[] currentFreq, int[] targetFreq) {28        for (int k = 0; k < 26; k++) {29            if (currentFreq[k] < targetFreq[k]) {30                return false;31            }32        }33        return true;34    }35}

• Pre-calculate targetFreq for word2 and count the number of unique characters in it, let's call this mismatches.
• Initialize totalCount = 0, left pointer i = 0, right pointer j = 0, and an empty currentFreq map.
• Loop i from 0 to word1.length() - 1:
  • While j < word1.length() and mismatches > 0:
    • Add word1.charAt(j) to currentFreq.
    • If currentFreq for this character now matches targetFreq, decrement mismatches.
    • Increment j.
  • If mismatches == 0, it means word1[i..j-1] is the first valid substring starting at i. All substrings starting at i and ending at j-1 or later are also valid. Add word1.length() - (j - 1) to totalCount.
  • Shrink the window from the left: Remove word1.charAt(i) from currentFreq.
  • If currentFreq for this character was exactly matching targetFreq before removal, it becomes deficient, so increment mismatches.
• Return totalCount.

We use two pointers, i (left) and j (right), to define a "window" on word1. The pointer i iterates from the beginning to the end of word1, representing the start of our potential substrings.

For each i, we expand the window by advancing j until the substring word1[i..j] becomes valid. To efficiently track validity, we maintain a count of "deficient" character types. Initially, this is the number of unique characters in word2. As we expand the window by including word1.charAt(j), we update our window's frequency map. If the count for a character c in our window matches the required count from word2, we decrement the deficient count.

Once the deficient count drops to zero, we have found the shortest valid substring starting at i. Let's say it ends at index j-1. Then we know that all substrings starting at i and ending at any index from j-1 to N-1 (where N is word1.length()) are also valid. The number of such substrings is N - (j-1). We add this to our total count.

We then slide the window forward by incrementing i. This involves removing word1.charAt(i) from our window's frequency map and updating the deficient count if this removal makes a previously satisfied character deficient again. The right pointer j does not reset, ensuring that each character in word1 is visited at most twice.

1class Solution {2    public long countSubstrings(String word1, String word2) {3        int n = word1.length();4        int[] targetFreq = new int[26];5        for (char c : word2.toCharArray()) {6            targetFreq[c - 'a']++;7        }8 9        int mismatches = 0;10        for (int count : targetFreq) {11            if (count > 0) {12                mismatches++;13            }14        }15 16        long totalCount = 0;17        int[] currentFreq = new int[26];18        int i = 0, j = 0;19 20        for (i = 0; i < n; i++) {21            // Expand window by moving right pointer j22            while (j < n && mismatches > 0) {23                char charJ = word1.charAt(j);24                currentFreq[charJ - 'a']++;25                if (currentFreq[charJ - 'a'] == targetFreq[charJ - 'a']) {26                    mismatches--;27                }28                j++;29            }30 31            // If window is valid, count all substrings starting at i32            if (mismatches == 0) {33                totalCount += (long)n - j + 1;34            }35 36            // Shrink window from the left by moving pointer i37            char charI = word1.charAt(i);38            if (targetFreq[charI - 'a'] > 0 && currentFreq[charI - 'a'] == targetFreq[charI - 'a']) {39                mismatches++;40            }41            currentFreq[charI - 'a']--;42        }43 44        return totalCount;45    }46}