当前位置: 首页 > news >正文

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&#xff1a;滑动窗口 力扣题目链接&#xff1a;https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/ 给你两个字符串 word1 和 word2 。 如果一个字符串 x 重新…...

如何在 Ubuntu 24.04 上安装 Memcached 服务器教程

简介 Memcached 是一个高性能、分布式的内存缓存系统&#xff0c;旨在通过减少数据库负载来加速动态 Web 应用程序。它通过将数据和对象缓存在 RAM 中来实现这一点&#xff0c;从而最大限度地减少了从数据库或其他慢速存储层重复获取数据的需要。 本教程的目标是手把手教你如…...

《深度学习模型在鸿蒙分布式框架下的跨设备高效之旅》

在人工智能领域&#xff0c;深度学习模型的训练与推理通常需要强大的计算资源和大量的数据支持。而鸿蒙系统的分布式框架为解决这一问题提供了新的思路和方法&#xff0c;使得深度学习模型能够在多个设备之间实现高效的训练与推理。 鸿蒙分布式框架概述 鸿蒙系统是一款面向万…...

[python3]Excel解析库-xlutils

xlutils 是一组用于处理 Excel 文件的 Python 库&#xff0c;它实际上是 xlrd 和 xlwt 的扩展&#xff0c;提供了额外的功能来操作 Excel 文件。xlutils 主要由三个部分组成&#xff1a;xlutils.copy、xlutils.filter 和 xlutils.view&#xff0c;它们分别用于复制和修改现有 E…...

Springboot Bean创建流程、三种Bean注入方式(构造器注入、字段注入、setter注入)、循坏依赖问题

文章目录 1 Bean 创建流程1.1 Bean的扫描注册1.2 创建Bean的顺序 2 三种Bean注入方式2.1 构造器注入 | Constructor Injection&#xff08;推荐&#xff09;2.2 字段注入 | Field Injection&#xff08;常用&#xff09;2.3 方法注入 | Setter Injection2.4 三种方式注入顺序 3…...

mybatisX插件的使用,以及打包成配置

装mybatisX插件&#xff1b; idea连接数据库&#xff1b; 点击mybatisx-generator&#xff0c;设置自己装mybatisX插件&#xff1b; idea连接数据库&#xff1b; 点击mybatisx-generator&#xff0c;设置自己要的包和类&#xff1b; 如果要把自己的配置设置成一个自定义模板&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# 常见的几种取整场景

软件取整&#xff0c;通常指的是在计算机软件中对数值进行取整操作&#xff0c;即将一个浮点数或小数转换为整数&#xff0c;同时确定如何处理小数部分。取整操作在编程和数学计算中非常常见&#xff0c;不同的取整方法适用于不同的场景。 常见的取整方法 向零取整&#xff08…...

数据库回滚:大祸临头时

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

【GoLang】两个字符串如何比较大小?以及字典顺序的比较规则

在 Go 语言中&#xff0c;字符串的比较是基于字典顺序进行的。 字典顺序的比较规则&#xff1a; 比较两个字符串从左到右逐个字符的Unicode码点值&#xff0c; 若比较结果不相等则将此结果作为字符串大小的结果&#xff0c; 若比较结果相等则比较下一位&#xff0c; 若其中一个…...

5G学习笔记之SNPN系列之UE入网和远程配置

参考&#xff1a;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封装&#xff0c;提供了丰富的图像处理和计算机视觉功能。以下是一些常用函数及其详细说明。 1. 图像读取与显示 Cv2.ImRead 功能&#xff1a;读取图像文件并返回一个 Mat 对象。用法&#xff1a;Mat image Cv2.ImRead("path/to/image.jpg&…...

Spring Boot教程之五十二:CrudRepository 和 JpaRepository 之间的区别

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

蓝桥杯备考:数据结构之栈 和 stack

栈的概念以及栈的实现 栈是一种只允许在一端进行插入和删除的线性表 空栈&#xff1a;没有任何元素 入栈&#xff1a;插入元素 出栈&#xff1a;删除元素 栈本身就是一个线性表&#xff0c;我们可以写一个足够大的数组来实现栈 除此之外&#xff0c;我们还需要变量n来记录…...

solidity基础 -- 映射

在区块链的智能合约开发领域&#xff0c;Solidity 作为以太坊上最主流的编程语言之一&#xff0c;拥有诸多强大特性助力开发者构建复杂且高效的去中心化应用。其中&#xff0c;映射&#xff08;Mapping&#xff09;是一个极为关键的数据结构&#xff0c;它为合约中的数据存储与…...

Angular 11课程实践:构建高效单页应用的支持代码

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

测试用例颗粒度说明

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

ESP32 IDF VScode出现头文件“无法打开 源 文件 ”,并有红色下划线警告

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

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\…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...