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

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.

View Leetcode Problem

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

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.