LeetCode 3297: Count Substrings That Can Be Rearranged to Contain a String I Solution

Master LeetCode problem 3297 (Count Substrings That Can Be Rearranged to Contain a String I), a medium 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.

3297. Count Substrings That Can Be Rearranged to Contain a String I

Medium

Hash Table String Sliding Window

Problem Explanation

Explanation

To solve this problem, we can iterate through all substrings of word1 and check if each substring can be rearranged to contain word2 as a prefix. We can achieve this by counting the frequency of characters in both word1 and word2. For each substring, we check if it has enough characters to form word2 as a prefix. If yes, we increment the count of valid substrings.

Algorithm

Initialize a variable count to store the count of valid substrings.
Count the frequency of characters in word2.
Iterate through all substrings of word1.
For each substring, count the frequency of characters.
Check if the substring has enough characters to form word2 as a prefix.
If yes, increment count.
Return the final count.

Time Complexity

The time complexity of this algorithm is O(n^2) where n is the length of word1. This is because we are iterating through all substrings of word1.

Space Complexity

The space complexity of this algorithm is O(1) since we are using a fixed-size array to store character frequencies.

Solution Code

class Solution {
    public int countSubstrings(String word1, String word2) {
        int count = 0;
        int[] freqWord2 = new int[26];
        
        for (char c : word2.toCharArray()) {
            freqWord2[c - 'a']++;
        }
        
        for (int i = 0; i < word1.length(); i++) {
            int[] freqWord1 = new int[26];
            for (int j = i; j < word1.length(); j++) {
                freqWord1[word1.charAt(j) - 'a']++;
                if (isPrefix(freqWord1, freqWord2)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private boolean isPrefix(int[] freq1, int[] freq2) {
        for (int i = 0; i < 26; i++) {
            if (freq1[i] < freq2[i]) {
                return false;
            }
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

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

This page provides optimized solutions for LeetCode problem 3297 (Count Substrings That Can Be Rearranged to Contain a String I) 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 3297 (Count Substrings That Can Be Rearranged to Contain a String I)?

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

Can I run code for LeetCode 3297 on DevExCode?

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

Back to LeetCode Solutions