LeetCode 3298: Count Substrings That Can Be Rearranged to Contain a String II Solution

Master LeetCode problem 3298 (Count Substrings That Can Be Rearranged to Contain a String II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

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

Hard

Hash Table String Sliding Window

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3298 (Count Substrings That Can Be Rearranged to Contain a String II)?

This page provides optimized solutions for LeetCode problem 3298 (Count Substrings That Can Be Rearranged to Contain a String II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3298 (Count Substrings That Can Be Rearranged to Contain a String II)?

The time complexity for LeetCode 3298 (Count Substrings That Can Be Rearranged to Contain a String II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3298 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3298 in Java, C++, or Python.

Back to LeetCode Solutions