Welcome to Subscribe On Youtube

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

Description

You are given two strings word1 and word2.

A string x is called valid if x can be rearranged to have word2 as a prefix.

Return the total number of valid substrings of word1.

 

Example 1:

Input: word1 = "bcca", word2 = "abc"

Output: 1

Explanation:

The only valid substring is "bcca" which can be rearranged to "abcc" having "abc" as a prefix.

Example 2:

Input: word1 = "abcabc", word2 = "abc"

Output: 10

Explanation:

All the substrings except substrings of size 1 and size 2 are valid.

Example 3:

Input: word1 = "abcabc", word2 = "aaabc"

Output: 0

 

Constraints:

  • 1 <= word1.length <= 105
  • 1 <= word2.length <= 104
  • word1 and word2 consist only of lowercase English letters.

Solutions

Solution 1: Sliding Window

The problem is essentially to find how many substrings in $\textit{word1}$ contain all the characters in $\textit{word2}$. We can use a sliding window to handle this.

First, if the length of $\textit{word1}$ is less than the length of $\textit{word2}$, then it is impossible for $\textit{word1}$ to contain all the characters of $\textit{word2}$, so we directly return $0$.

Next, we use a hash table or an array of length $26$ called $\textit{cnt}$ to count the occurrences of characters in $\textit{word2}$. Then, we use $\textit{need}$ to record how many more characters are needed to meet the condition, initialized to the length of $\textit{cnt}$.

We then use a sliding window $\textit{win}$ to record the occurrences of characters in the current window. We use $\textit{ans}$ to record the number of substrings that meet the condition, and $\textit{l}$ to record the left boundary of the window.

We traverse each character in $\textit{word1}$. For the current character $c$, we add it to $\textit{win}$. If the value of $\textit{win}[c]$ equals $\textit{cnt}[c]$, it means the current window already contains one of the characters in $\textit{word2}$, so we decrement $\textit{need}$ by one. If $\textit{need}$ equals $0$, it means the current window contains all the characters in $\textit{word2}$. We need to shrink the left boundary of the window until $\textit{need}$ is greater than $0$. Specifically, if $\textit{win}[\textit{word1}[l]]$ equals $\textit{cnt}[\textit{word1}[l]]$, it means the current window contains one of the characters in $\textit{word2}$. After shrinking the left boundary, it no longer meets the condition, so we increment $\textit{need}$ by one and decrement $\textit{win}[\textit{word1}[l]]$ by one. Then, we increment $\textit{l}$ by one. At this point, the window is $[l, r]$. For any $0 \leq l’ < l$, $[l’, r]$ are substrings that meet the condition, and there are $l$ such substrings, which we add to the answer.

After traversing all characters in $\textit{word1}$, we get the answer.

The time complexity is $O(n + m)$, where $n$ and $m$ are the lengths of $\textit{word1}$ and $\textit{word2}$, respectively. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set. Here, it is the set of lowercase letters, so the space complexity is constant.

  • class Solution {
        public long validSubstringCount(String word1, String word2) {
            if (word1.length() < word2.length()) {
                return 0;
            }
            int[] cnt = new int[26];
            int need = 0;
            for (int i = 0; i < word2.length(); ++i) {
                if (++cnt[word2.charAt(i) - 'a'] == 1) {
                    ++need;
                }
            }
            long ans = 0;
            int[] win = new int[26];
            for (int l = 0, r = 0; r < word1.length(); ++r) {
                int c = word1.charAt(r) - 'a';
                if (++win[c] == cnt[c]) {
                    --need;
                }
                while (need == 0) {
                    c = word1.charAt(l) - 'a';
                    if (win[c] == cnt[c]) {
                        ++need;
                    }
                    --win[c];
                    ++l;
                }
                ans += l;
            }
            return ans;
        }
    }
    
    
  • class Solution {
    public:
        long long validSubstringCount(string word1, string word2) {
            if (word1.size() < word2.size()) {
                return 0;
            }
            int cnt[26]{};
            int need = 0;
            for (char& c : word2) {
                if (++cnt[c - 'a'] == 1) {
                    ++need;
                }
            }
            long long ans = 0;
            int win[26]{};
            int l = 0;
            for (char& c : word1) {
                int i = c - 'a';
                if (++win[i] == cnt[i]) {
                    --need;
                }
                while (need == 0) {
                    i = word1[l] - 'a';
                    if (win[i] == cnt[i]) {
                        ++need;
                    }
                    --win[i];
                    ++l;
                }
                ans += l;
            }
            return ans;
        }
    };
    
    
  • class Solution:
        def validSubstringCount(self, word1: str, word2: str) -> int:
            if len(word1) < len(word2):
                return 0
            cnt = Counter(word2)
            need = len(cnt)
            ans = l = 0
            win = Counter()
            for c in word1:
                win[c] += 1
                if win[c] == cnt[c]:
                    need -= 1
                while need == 0:
                    if win[word1[l]] == cnt[word1[l]]:
                        need += 1
                    win[word1[l]] -= 1
                    l += 1
                ans += l
            return ans
    
    
  • func validSubstringCount(word1 string, word2 string) int64 {
    
    }
    
    
  • function validSubstringCount(word1: string, word2: string): number {}
    
    

All Problems

All Solutions