LeetCode 3297.统计重新排列后包含另一个字符串的子字符串数目 I:滑动窗口
【LetMeFly】3297.统计重新排列后包含另一个字符串的子字符串数目 I:滑动窗口
力扣题目链接:https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/
给你两个字符串 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 <= 105
1 <= word2.length <= 104
word1
和word2
都只包含小写英文字母。
解题方法:滑动窗口
首先统计word2
中每个字符分别出现了多少次,接着开始滑动窗口:
窗口起点是
word1
的每个字符,窗口终点是第一次“合法”的最小结束位置。
对于一个起点l
,若最小合法位置是r
,则合法方案是[l, r]
、[l, r + 1]
、...
、[l, len(word1) - 1]
。
- 时间复杂度 O ( l e n ( w o r d 1 ) × C + l e n ( w o r d 2 ) ) O(len(word1)\times C+len(word2)) O(len(word1)×C+len(word2)),其中 C = 26 C=26 C=26
- 空间复杂度 O ( C ) O(C) O(C)
AC代码
C++
/** @Author: LetMeFly* @Date: 2025-01-09 11:03:16* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-09 12:39:10*/
typedef long long ll;
class Solution {
private:bool ok(int* cnt1, int* cnt2) {for (int i = 0; i < 26; i++) {if (cnt1[i] < cnt2[i]) {return false;}}return true;}
public:ll validSubstringCount(string& word1, string& word2) {int cnt1[26] = {0}, cnt2[26] = {0};for (char c : word2) {cnt2[c - 'a']++;}ll ans = 0;for (int l = 0, r = 0; l < word1.size(); l++, r = max(r, l)) {if (l) {cnt1[word1[l - 1] - 'a']--;}while (!ok(cnt1, cnt2)) {if (r == word1.size()) {return ans;}cnt1[word1[r++] - 'a']++;}ans += word1.size() - r + 1;}return ans;}
};#ifdef _WIN32
/*
bcca
abc1
*/
/*
abcabc
abc10
*/
int main() {Solution sol;string a, b;while (cin >> a >> b) {cout << sol.validSubstringCount(a, b) << endl;}return 0;
}
#endif
Python
'''
Author: LetMeFly
Date: 2025-01-09 12:39:58
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-09 12:44:30
'''
from collections import Counter, defaultdictclass Solution:def ok(self, cnt1: defaultdict) -> bool:for k, v in self.cnt2.items():if cnt1[k] < v:return Falsereturn Truedef validSubstringCount(self, word1: str, word2: str) -> int:self.cnt2 = Counter(word2)cnt1 = defaultdict(int)ans = l = r = 0while l < len(word1):if l:cnt1[word1[l - 1]] -= 1while not self.ok(cnt1):if r == len(word1):return anscnt1[word1[r]] += 1r += 1ans += len(word1) - r + 1l += 1return ans
Java
/** @Author: LetMeFly* @Date: 2025-01-09 12:46:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-09 12:51:13*/
class Solution {private boolean ok(int[] a, int[] b) {for (int i = 0; i < 26; i++) {if (a[i] < b[i]) {return false;}}return true;}public long validSubstringCount(String word1, String word2) {int[] cnt1 = new int[26], cnt2 = new int[26];for (char c : word2.toCharArray()) {cnt2[c - 'a']++;}long ans = 0;for (int l = 0, r = 0; l < word1.length(); l++) {if (l > 0) {cnt1[word1.charAt(l - 1) - 'a']--;}while (!ok(cnt1, cnt2)) {if (r == word1.length()) {return ans;}cnt1[word1.charAt(r++) - 'a']++;}ans += word1.length() - r + 1;}return ans;}
}
Go
/** @Author: LetMeFly* @Date: 2025-01-09 12:52:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-09 13:10:20*/
package main// import "fmt"func ok(a, b []int) bool {for i := range a {if a[i] < b[i] {return false}}return true
}func validSubstringCount(word1 string, word2 string) (ans int64) {cnt1, cnt2 := make([]int, 26), make([]int, 26)for _, c := range word2 {cnt2[c - 'a']++}// fmt.Println(cnt2)for l, r := 0, 0; l < len(word1); l++ {if l > 0 {cnt1[word1[l - 1] - 'a']--}for !ok(cnt1, cnt2) {if r == len(word1) {return}cnt1[word1[r] - 'a']++r++}// fmt.Println(cnt1)// fmt.Println(r)ans += int64(len(word1) - r + 1)}return
}
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/145031494
相关文章:
LeetCode 3297.统计重新排列后包含另一个字符串的子字符串数目 I:滑动窗口
【LetMeFly】3297.统计重新排列后包含另一个字符串的子字符串数目 I:滑动窗口 力扣题目链接:https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/ 给你两个字符串 word1 和 word2 。 如果一个字符串 x 重新…...
如何在 Ubuntu 24.04 上安装 Memcached 服务器教程
简介 Memcached 是一个高性能、分布式的内存缓存系统,旨在通过减少数据库负载来加速动态 Web 应用程序。它通过将数据和对象缓存在 RAM 中来实现这一点,从而最大限度地减少了从数据库或其他慢速存储层重复获取数据的需要。 本教程的目标是手把手教你如…...
《深度学习模型在鸿蒙分布式框架下的跨设备高效之旅》
在人工智能领域,深度学习模型的训练与推理通常需要强大的计算资源和大量的数据支持。而鸿蒙系统的分布式框架为解决这一问题提供了新的思路和方法,使得深度学习模型能够在多个设备之间实现高效的训练与推理。 鸿蒙分布式框架概述 鸿蒙系统是一款面向万…...
[python3]Excel解析库-xlutils
xlutils 是一组用于处理 Excel 文件的 Python 库,它实际上是 xlrd 和 xlwt 的扩展,提供了额外的功能来操作 Excel 文件。xlutils 主要由三个部分组成:xlutils.copy、xlutils.filter 和 xlutils.view,它们分别用于复制和修改现有 E…...
Springboot Bean创建流程、三种Bean注入方式(构造器注入、字段注入、setter注入)、循坏依赖问题
文章目录 1 Bean 创建流程1.1 Bean的扫描注册1.2 创建Bean的顺序 2 三种Bean注入方式2.1 构造器注入 | Constructor Injection(推荐)2.2 字段注入 | Field Injection(常用)2.3 方法注入 | Setter Injection2.4 三种方式注入顺序 3…...

mybatisX插件的使用,以及打包成配置
装mybatisX插件; idea连接数据库; 点击mybatisx-generator,设置自己装mybatisX插件; idea连接数据库; 点击mybatisx-generator,设置自己要的包和类; 如果要把自己的配置设置成一个自定义模板&a…...

【初阶数据结构】线性表之单链表
文章目录 前言 一、单链表的概念与结构 1.概念 2.结点 3.性质 二、实现单链表 1.结构的定义 2.链表的打印和结点的申请 3.单链表的尾插和头插 4.单链表的尾删和头删 5.单链表的查找 6.指定位置之前插入数据和指定位置之后插入数据 7.删除pos结点和删除pos之后的结…...

CentOS7通过yum安装JDK
CentOS7通过yum安装JDK 1、卸载自带的JDK 查看已安装的JDK rpm -qa | grep java删除已安装的JDK yum -y remove java-1.8.0-openjdk*验证是否删除成功 查不到版本信息则已删除成功 java -version2、安装JDK sudo yum install java-1.8.0-openjdk java-1.8.0-openjdk-deve…...
c# 常见的几种取整场景
软件取整,通常指的是在计算机软件中对数值进行取整操作,即将一个浮点数或小数转换为整数,同时确定如何处理小数部分。取整操作在编程和数学计算中非常常见,不同的取整方法适用于不同的场景。 常见的取整方法 向零取整(…...

数据库回滚:大祸临头时
原文地址 什么是数据库回滚? 数据库技术中,回滚是通过撤销对数据库所做的一项或多项更改,将数据库返回到先前状态的操作。它是维护数据完整性和从错误中恢复的重要机制。 什么时候需要数据库回滚? 数据库回滚在以下几个场景中很…...

【GoLang】两个字符串如何比较大小?以及字典顺序的比较规则
在 Go 语言中,字符串的比较是基于字典顺序进行的。 字典顺序的比较规则: 比较两个字符串从左到右逐个字符的Unicode码点值, 若比较结果不相等则将此结果作为字符串大小的结果, 若比较结果相等则比较下一位, 若其中一个…...

5G学习笔记之SNPN系列之UE入网和远程配置
参考:3GPP 23.501 5.30.2.10 Onboarding of UEs for SNPNs 小小协议搬运工 目录 0. NPN系列 1. 概述 2. SNPN作为ONN 2.1 DCS参与的入网主鉴权 2.2 DCS不参与的入网主鉴权 2.3 UE入网 3. PLMN作为ONN 4. 远程配置 0. NPN系列 1. NPN概述 2. NPN R18 3. 【SNPN系列】…...

C#版OpenCv常用函数大全
OpenCvSharp 是 OpenCV 的NET封装,提供了丰富的图像处理和计算机视觉功能。以下是一些常用函数及其详细说明。 1. 图像读取与显示 Cv2.ImRead 功能:读取图像文件并返回一个 Mat 对象。用法:Mat image Cv2.ImRead("path/to/image.jpg&…...

Spring Boot教程之五十二:CrudRepository 和 JpaRepository 之间的区别
Spring Boot – CrudRepository 和 JpaRepository 之间的区别 Spring Boot建立在 Spring 之上,包含 Spring 的所有功能。由于其快速的生产就绪环境,使开发人员能够直接专注于逻辑,而不必费力配置和设置,因此如今它正成为开发人员…...

蓝桥杯备考:数据结构之栈 和 stack
栈的概念以及栈的实现 栈是一种只允许在一端进行插入和删除的线性表 空栈:没有任何元素 入栈:插入元素 出栈:删除元素 栈本身就是一个线性表,我们可以写一个足够大的数组来实现栈 除此之外,我们还需要变量n来记录…...
solidity基础 -- 映射
在区块链的智能合约开发领域,Solidity 作为以太坊上最主流的编程语言之一,拥有诸多强大特性助力开发者构建复杂且高效的去中心化应用。其中,映射(Mapping)是一个极为关键的数据结构,它为合约中的数据存储与…...

Angular 11课程实践:构建高效单页应用的支持代码
本文还有配套的精品资源,点击获取 简介:Angular 11是Google支持的前端框架,适合构建复杂的单页应用(SPA)。本课程将深入介绍Angular核心特性,如组件化、依赖注入、数据绑定和路由,并且涵盖Ang…...

测试用例颗粒度说明
当我们在编写测试用例时,总是会遇到一个问题:如何确定测试用例的颗粒度?测试用例过于粗糙,可能无法全面覆盖系统的细节;而颗粒度过细,又会导致测试重复、冗余。掌握合适的颗粒度,不仅可以提高测…...

ESP32 IDF VScode出现头文件“无法打开 源 文件 ”,并有红色下划线警告
问题背景: ESP32 IDF VScode出现头文件“无法打开 源 文件 ”,并有红色下划线警告: 解决办法: 在工程里面的.vscode文件夹下,检查是否存在c_cpp_properties.json文件,如果没有可以手动创建添加。如图…...

Windows安装ES单机版设置密码
下载ES ES下载链接 我用的是7.17.26 启动前配置 解压之后打开D:\software\elasticsearch-7.17.26\bin\elasticsearch-env.bat 在elasticsearch-env.bat文件中修改jdk的路径 修改前 修改内容 if defined ES_JAVA_HOME (set JAVA"D:\software\elasticsearch-7.17.26\…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...

AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
Vue 模板语句的数据来源
🧩 Vue 模板语句的数据来源:全方位解析 Vue 模板(<template> 部分)中的表达式、指令绑定(如 v-bind, v-on)和插值({{ }})都在一个特定的作用域内求值。这个作用域由当前 组件…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...