1208. 尽可能使字符串相等

Problem: 1208. 尽可能使字符串相等

题目描述

给定两个相同长度的字符串 st,将字符串 s 转换为字符串 t 需要消耗开销,开销是两个字符的 ASCII 码差值的绝对值。还有一个最大预算 maxCost,我们需要在这个预算范围内,找到 s 中能够转换为 t 的最长子字符串,返回这个子字符串的长度。

示例

示例 1:

输入:s = "abcd", t = "bcdf", maxCost = 3
输出:3
解释:将 "abc" 变为 "bcd" 的总开销为 3,所以最长可转换子字符串长度为 3。

示例 2:

输入:s = "abcd", t = "cdef", maxCost = 3
输出:1
解释:每个字符的转换开销都为 2,因此只能转换单个字符。

代码实现

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.length(), ans = 0, left = 0;
        int window = 0;

        for (int right = 0; right < n; right++) {
            int c = abs(s[right] - t[right]);  // 计算当前字符转换开销
            window += c;  // 累计窗口内的总开销

            // 当总开销超过 maxCost 时,移动左指针缩小窗口
            while (window > maxCost) {
                window -= abs(s[left] - t[left]);  // 移除左边的开销
                left++;
            }

            // 更新最大可转换子字符串的长度
            ans = max(ans, right - left + 1);
        }

        return ans;
    }
};

题解

1. 解题思路

这道题可以用滑动窗口来解决。滑动窗口是一种常见的算法思想,它通过动态调整窗口的大小来解决问题。具体步骤如下:

  • 使用两个指针 leftright 来表示窗口的左右边界,left 是窗口的起点,right 是窗口的终点。
  • 在遍历字符串的过程中,不断累加从 s 转换到 t 的字符开销。
  • 如果当前窗口内的总开销超过了 maxCost,则移动 left 指针缩小窗口,直到总开销重新符合条件。
  • 在每次符合条件时,计算并更新当前可转换的最大子字符串长度。
2. 变量解释
  • n: 字符串 st 的长度,假设两者长度相同。
  • left: 滑动窗口的左边界,用来控制窗口缩小。
  • right: 滑动窗口的右边界,用来控制窗口扩大。
  • window: 记录当前窗口内的转换开销总和。
  • c: 当前窗口中 s[right] 转换为 t[right] 的开销,即 abs(s[right] - t[right])
  • ans: 最终的答案,表示最长的可转换子字符串长度。
3. 滑动窗口详解

滑动窗口的核心在于:

  • 当总开销 window 小于等于 maxCost 时,我们可以扩大窗口的右边界 right,并更新当前窗口的长度。
  • 当总开销 window 超过 maxCost 时,需要移动左边界 left,缩小窗口,直到开销重新回到预算范围内。

通过这种方式,我们可以在 O(n) 的时间复杂度下完成遍历,并且只使用了常量空间 O(1),因此该解法非常高效。

4. 代码逻辑解析
  • 首先初始化 leftright 指针,window 用于记录当前窗口的总开销。
  • for 循环中,遍历字符串的每一个字符,计算转换的开销,并更新 window
  • 如果 window 超过了 maxCost,通过 while 循环移动 left 指针,缩小窗口,并减少开销。
  • 每次窗口有效时,更新最大可转换子字符串的长度。

时间复杂度和空间复杂度

  • 时间复杂度:O(n),其中 n 是字符串的长度。每个字符最多被访问两次(一次进入窗口,一次离开窗口)。
  • 空间复杂度:O(1),只使用了常数空间来记录窗口的状态。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/899484.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于知识图谱的诗词推荐系统

你是否曾经想在浩如烟海的古代诗词中找到属于自己的那几首“知己”&#xff1f;现在&#xff0c;借助人工智能与知识图谱&#xff0c;古典诗词不再是玄之又玄的文本&#xff0c;而是变成了让你“个性化定制”的文化体验&#xff01;我们带来的这款基于知识图谱的诗词推荐系统&a…

我准备写一份Stable Diffusion入门指南-part1

我准备写个SD自学指南&#xff0c;当然也是第一次写&#xff0c;可能有点凌乱&#xff0c;后续我会持续更新不断优化&#xff0c;我是生产队的驴&#xff0c;欢迎监督。 Stable Diffusion WebUI 入门指南 Stable Diffusion WebUI 是一款基于 Stable Diffusion 模型的用户界面…

SIP 业务举例之 Transfer - Unattended(无人值守呼叫转移)

目录 1. Transfer - Unattended 简介 2. IP Telephony 特性 3. RFC5359 的 Transfer - Unattended 信令流程 无人值守呼叫转移 隐式订阅 Bob 通知 Alice 呼叫转移完成 - NOTIFY 隐含的订阅和显示的订阅 4. Transfer - Unattended 过程总结 博主wx:yuanlai45_csdn 博主…

重写 CSS Flexible Box

一、是什么? Flex 是 Flexible Box 的缩写, 意为 弹性布局, 用来为盒状模型提供更为灵活的布局能力, 它给 Flexbox 的 子元素 之间提供了强大的 空间分布(伸缩) 和 对齐 能力 二、基础概念 2.1 容器 采用 Flex 布局的元素 (设置了 display: flex | inline-flex 的元素) 称…

轻松上手 Disruptor:两个实例解析并发编程利器

Disruptor 是英国外汇交易公司 LMAX 开发的一个高性能队列。很多知名开源项目里&#xff0c;比如 canal 、log4j2、 storm 都是用了 Disruptor 以提升系统性能 。 这篇文章&#xff0c;我们通过两个例子一步一个脚印帮助同学们入门 Disruptor 。 1 环形缓冲区 下图展示了 Di…

详解Oracle审计(一)

题记&#xff1a; 有段时间没写过oracle了&#xff0c;今天回归。 本文将详细介绍oracle的审计功能&#xff0c;基于11g版本&#xff0c;但对12c&#xff0c;19c也同样适用。 审计&#xff08;Audit&#xff09;用于监视用户所执行的数据库操作&#xff0c;并且 Oracle 会将审…

hadoop的yarn

1.分布式的资源调度-yarn(hadoop的一个组件) 资源服务器硬件资源&#xff0c;如&#xff1a;CPU,内存,硬盘,网络等 资源调度:管控服务器硬件资源&#xff0c;提供更好的利用率 分布式资源调度:管控整个分布式服务器集群的全部资源&#xff0c;整合进行统一调度 总结就是使用yar…

chatGpt4.0Plus,Claude3最新保姆级教程开通升级

如何使用 WildCard 服务注册 Claude3 随着 Claude3 的震撼发布&#xff0c;最强 AI 模型的桂冠已不再由 GPT-4 独揽。Claude3 推出了三个备受瞩目的模型&#xff1a;Claude 3 Haiku、Claude 3 Sonnet 以及 Claude 3 Opus&#xff0c;每个模型都展现了卓越的性能与特色。其中&a…

Blazor WebAssembly 项目部署时遇到 500.19错误

这个错误其实很普遍&#xff0c;在部署 asp.net core 的时候都能解决 无非是安装 这些, 尤其是下面那个 Hosting Bundle 但是遇到 Blazor WebAssembly 项目部署时还得多装一个 “重写模块” 下载地址&#xff0c;安装后重启网址 https://www.iis.net/downloads/microsoft/u…

【从零开始的LeetCode-算法】3185. 构成整天的下标对数目 II

给你一个整数数组 hours&#xff0c;表示以 小时 为单位的时间&#xff0c;返回一个整数&#xff0c;表示满足 i < j 且 hours[i] hours[j] 构成 整天 的下标对 i, j 的数目。 整天 定义为时间持续时间是 24 小时的 整数倍 。 例如&#xff0c;1 天是 24 小时&#xff0c…

使用Vue指令实现面板拉伸功能

目的&#xff1a;现在有一个PDF预览页面&#xff0c;左侧为PDF预览区域&#xff0c;右侧为可以进行AI功能的面板。现在想让AI面板通过拖动左边框实现面板拉伸。 实现效果如下面的视频&#xff1a; 关键点&#xff1a; 预览区是使用iframe渲染的&#xff0c;在拖动的过程中&…

软件测试学习笔记丨Selenium键盘鼠标事件ActionChains

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/22515 本文为霍格沃兹测试开发学社的学习经历分享&#xff0c;写出来分享给大家&#xff0c;希望有志同道合的小伙伴可以一起交流技术&#xff0c;一起进步~ 说明&#xff1a;本篇博客基于sel…

Detecting Holes in Point Set Surfaces 论文阅读

下载链接 Detecting Holes in Point Set Surfaces 摘要 3D 数据采集过程&#xff08;例如激光范围扫描&#xff09;产生的重要物体模型通常包含由于遮挡、反射或透明度而产生的孔洞。本文的目标就是在点集表面上检测存在的孔洞。对于每个点&#xff0c;将多个标准组合成一个综…

C# shader 生成程序纹理

1、程序纹理是什么 程序纹理&#xff08;Procedural Textures&#xff09;就是通过程序代码生成的纹理 2、程序纹理如何生成 一般生成程序纹理由两种方式&#xff1a; 通过C#脚本生成纹理后传递给Shader直接在Shader代码中自定义逻辑生成纹理 3、程序纹理的好处 程序纹理…

2.1 > Shell 是什么、如何更熟练的使用 Bash Shell

Shell 基础知识 Shell是计算机操作系统中的一个命令行解释器&#xff0c;由C语言编写&#xff0c;用于用户与操作系统之间进行交互。用户可以通过Shell输入命令&#xff0c;操作系统接收到这些命令后执行相应的操作。Shell一般还提供了编程语言的基本功能&#xff0c;允许用户…

梯度累积的隐藏陷阱:Transformer库中梯度累积机制的缺陷与修正

在本地环境下对大规模语言模型&#xff08;LLMs&#xff09;进行微调时&#xff0c;由于GPU显存限制&#xff0c;采用大批量训练通常难以实现。为解决此问题&#xff0c;一般普遍会采用梯度累积技术来模拟较大的批量规模。该方法不同于传统的每批次更新模型权重的方式&#xff…

MacOS RocketMQ安装

MacOS RocketMQ安装 文章目录 MacOS RocketMQ安装一、下载二、安装修改JVM参数启动关闭测试关闭测试测试收发消息运行自带的生产者测试类运行自带的消费者测试类参考博客&#xff1a;https://blog.csdn.net/zhiyikeji/article/details/140911649 一、下载 打开官网&#xff0c;…

A-【项目开发知识管理】Android AIDL跨进程通信

Android AIDL跨进程通信 文章目录 Android AIDL跨进程通信0.我为啥要写这篇文章1.AIDL是干啥的&#xff1f;1.1简述1.2官方话 2.在AndroidStudio中怎么干&#xff1f;2.1准备工作2.2在项目A中创建AIDL文件夹2.3在项目A中创建一个aidl文件2.4将项目A进行一次Rebuild操作2.5在项目…

visual studio设置修改文件字符集方法

该方法来自网文&#xff0c;特此记录备忘。 添加两个组件&#xff0c;分别是Force UTF-8,FileEncoding。 截图如下&#xff1a; 方法如下&#xff1a;vs中点击“扩展”->“管理扩展”&#xff0c;输入utf搜索&#xff0c;安装如下两个插件&#xff0c;然后重启vs&#xf…

【设计模式系列】观察者模式

一、什么是观察者模式 观察者模式&#xff08;Observer Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了对象之间的一对多依赖关系&#xff0c;当一个对象的状态发生变化时&#xff0c;所有依赖于它的对象都会得到通知并自动更新。这种模式也被称为发布-订阅模式&…