3298. Count Substrings That Can Be Rearranged to Contain a String II

Explanation:

To solve this problem, we can use a sliding window technique. We iterate over each character in word1 and maintain a count of characters seen so far. For each character, we update our count and check if the current window of characters can be rearranged to form word2. We do this by comparing the count of characters in the window with the count of characters in word2.

Algorithm:

Initialize variables result, countWord1 and countWord2 to keep track of the total valid substrings, the count of characters in the current window, and the count of characters in word2 respectively.
Iterate over each character in word1 and update the count of that character in the window.
Check if the window size is greater than or equal to the length of word2.
If the window size is greater than the length of word2, we remove the first character from the window and update the counts accordingly.
Check if the counts of characters in the window match the counts of characters in word2. If they match, increment the result.
Return the final result.

Time Complexity: O(N), where N is the length of word1. Space Complexity: O(1), as we are using a constant amount of space.

:

View Leetcode Problem

class Solution {
    public int countSubstrings(String word1, String word2) {
        int result = 0;
        int[] countWord1 = new int[26];
        int[] countWord2 = new int[26];
        
        for (char c : word2.toCharArray()) {
            countWord2[c - 'a']++;
        }
        
        int left = 0;
        for (int right = 0; right < word1.length(); right++) {
            char curr = word1.charAt(right);
            countWord1[curr - 'a']++;
            
            if (right - left + 1 > word2.length()) {
                char leftChar = word1.charAt(left);
                countWord1[leftChar - 'a']--;
                left++;
            }
            
            if (right - left + 1 == word2.length()) {
                if (Arrays.equals(countWord1, countWord2)) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation:

Code Editor (Testing phase)

Improve Your Solution