Medium

题目描述

给你两个字符串 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^5
  • 1 <= word2.length <= 10^4
  • word1 和 word2 只包含小写英文字母。

解题思路

解题思路

这道题要求找出 word1 中有多少个子字符串可以重新排列后使得 word2 成为其前缀。

核心观察：如果一个字符串 x 可以重新排列使得 word2 成为其前缀，那么 x 中每个字符的频次必须大于等于 word2 中对应字符的频次。

滑动窗口解法：

  1. 首先统计 word2 中每个字符的频次作为需求
  2. 使用滑动窗口遍历 word1，维护当前窗口内字符的频次
  3. 对于每个右端点 right，找到最小的左端点 left 使得窗口 [left, right] 包含足够的字符
  4. 一旦找到这样的窗口，所有以 right 为右端点且左端点 <= left 的子字符串都是有效的

优化细节：

  • 使用变量 need 记录还需要满足的字符种类数
  • 当某个字符的频次刚好满足要求时，need--
  • 当 need == 0 时，当前窗口有效

时间复杂度为 O(n)，其中 n 是 word1 的长度，因为左右指针都最多移动 n 次。

代码实现

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']++;
            
            // 如果当前字符的频次刚好满足需求
            if (need[c - 'a'] > 0 && window[c - 'a'] == need[c - 'a']) {
                formed++;
            }
            
            // 当窗口满足条件时，尝试缩小窗口
            while (left <= right && formed == required) {
                result += left + 1;  // 以 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 Counter
        
        need = Counter(word2)
        required = len(need)
        
        window = {}
        left = 0
        formed = 0
        result = 0
        
        for right in range(len(word1)):
            char = word1[right]
            window[char] = window.get(char, 0) + 1
            
            if char in need and window[char] == need[char]:
                formed += 1
            
            while left <= right and formed == required:
                result += left + 1
                
                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;
        
        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']++;
            
            if (need[c - 'a'] > 0 && window[c - 'a'] == need[c - 'a']) {
                formed++;
            }
            
            while (left <= right && formed == required) {
                result += left + 1;
                
                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;
    
    for (const c of word2) {
        const idx = c.charCodeAt(0) - 97;
        if (need[idx]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n + m)n 为 word1 长度，m 为 word2 长度，每个字符最多被访问两次
空间复杂度O(1)只使用固定大小的数组存储字符频次（26个字母）

相关题目