Hard

题目描述

给定两个字符串 word1 和 word2。

如果字符串 x 能够重新排列使得 word2 成为其前缀，那么称字符串 x 为有效的。

返回 word1 的有效子字符串的总数。

注意：这个问题中的内存限制比通常更小，所以你必须实现一个线性运行时复杂度的解决方案。

示例 1：

输入：word1 = "bcca", word2 = "abc"
输出：1
解释：唯一的有效子字符串是 "bcca"，可以重新排列为 "abcc"，其中 "abc" 是前缀。

示例 2：

输入：word1 = "abcabc", word2 = "abc"
输出：10
解释：除了长度为 1 和长度为 2 的子字符串外，所有子字符串都是有效的。

示例 3：

输入：word1 = "abcabc", word2 = "aaabc"
输出：0

约束：

  • 1 <= word1.length <= 10^6
  • 1 <= word2.length <= 10^4
  • word1 和 word2 只包含小写英文字母

提示：

  • 使用滑动窗口和双指针
  • 使用常数空间存储字符频率

解题思路

这是一道经典的滑动窗口问题。关键在于理解什么是"有效子字符串"：一个子字符串是有效的，当且仅当它包含 word2 中每个字符至少对应的数量。

解题思路：

  1. 字符频率统计：首先统计 word2 中每个字符的出现次数，这是我们需要满足的最小要求。

  2. 滑动窗口：使用双指针技术维护一个滑动窗口：

    • left 指针：窗口的左边界
    • right 指针：窗口的右边界，不断向右扩展

  3. 窗口扩展与收缩：

    • 扩展：移动 right 指针，将新字符加入窗口
    • 收缩：当窗口满足条件时，尝试移动 left 指针缩小窗口
    • 每当窗口满足条件时，从当前 left 到字符串末尾的所有右端点都能形成有效子字符串

  4. 计数技巧：对于每个满足条件的窗口 [left, right]，以 left 为起点、以 [right, n-1] 为终点的子字符串都是有效的，共有 n - right 个。

  5. 优化：使用 need 变量记录还需要多少个不同字符才能满足条件，避免每次都遍历整个频率数组。

**时间复杂度：**O(n)，其中 n 是 word1 的长度
**空间复杂度：**O(1)，只使用固定大小的字符频率数组

代码实现

class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        vector<int> need(26, 0);
        int required = 0;
        
        // 统计word2中每个字符的需求量
        for (char c : word2) {
            if (need[c - 'a'] == 0) {
                required++;
            }
            need[c - 'a']++;
        }
        
        vector<int> window(26, 0);
        int left = 0, formed = 0;
        long long result = 0;
        
        for (int right = 0; right < word1.length(); right++) {
            char c = word1[right];
            window[c - 'a']++;
            
            // 如果当前字符的频率满足需求，增加formed
            if (need[c - 'a'] > 0 && window[c - 'a'] == need[c - 'a']) {
                formed++;
            }
            
            // 尝试收缩窗口
            while (left <= right && formed == required) {
                // 当前窗口满足条件，计算以left为起点的有效子字符串数量
                result += word1.length() - right;
                
                char leftChar = word1[left];
                window[leftChar - 'a']--;
                if (need[leftChar - 'a'] > 0 && window[leftChar - 'a'] < need[leftChar - 'a']) {
                    formed--;
                }
                left++;
            }
        }
        
        return result;
    }
};

class Solution:
    def validSubstringCount(self, word1: str, word2: str) -> int:
        from collections import defaultdict
        
        # 统计word2中每个字符的需求量
        need = defaultdict(int)
        for c in word2:
            need[c] += 1
        
        required = len(need)
        window = defaultdict(int)
        left = 0
        formed = 0
        result = 0
        
        for right in range(len(word1)):
            c = word1[right]
            window[c] += 1
            
            # 如果当前字符的频率满足需求，增加formed
            if c in need and window[c] == need[c]:
                formed += 1
            
            # 尝试收缩窗口
            while left <= right and formed == required:
                # 当前窗口满足条件，计算以left为起点的有效子字符串数量
                result += len(word1) - right
                
                left_char = word1[left]
                window[left_char] -= 1
                if left_char in need and window[left_char] < need[left_char]:
                    formed -= 1
                left += 1
        
        return result

public class Solution {
    public long ValidSubstringCount(string word1, string word2) {
        int[] need = new int[26];
        int required = 0;
        
        // 统计word2中每个字符的需求量
        foreach (char c in word2) {
            if (need[c - 'a'] == 0) {
                required++;
            }
            need[c - 'a']++;
        }
        
        int[] window = new int[26];
        int left = 0, formed = 0;
        long result = 0;
        
        for (int right = 0; right < word1.Length; right++) {
            char c = word1[right];
            window[c - 'a']++;
            
            // 如果当前字符的频率满足需求，增加formed
            if (need[c - 'a'] > 0 && window[c - 'a'] == need[c - 'a']) {
                formed++;
            }
            
            // 尝试收缩窗口
            while (left <= right && formed == required) {
                // 当前窗口满足条件，计算以left为起点的有效子字符串数量
                result += word1.Length - right;
                
                char leftChar = word1[left];
                window[leftChar - 'a']--;
                if (need[leftChar - 'a'] > 0 && window[leftChar - 'a'] < need[leftChar - 'a']) {
                    formed--;
                }
                left++;
            }
        }
        
        return result;
    }
}

var validSubstringCount = function(word1, word2) {
    const need = new Array(26).fill(0);
    let required = 0;
    
    // 统计word2中每个字符的需求量
    for (const c of word2) {
        const idx = c.charCodeAt(0) - 97;
        if (need[idx]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + m)
空间复杂度O(1)

其中 n 是 word1 的长度，m 是 word2 的长度。空间复杂度为常数级别，因为我们只使用了固定大小的字符频率数组（26个英文字母）。

相关题目