前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >获取满足指数的最长字符串

获取满足指数的最长字符串

作者头像
benym
发布2022-07-14 16:55:20
3860
发布2022-07-14 16:55:20
举报
文章被收录于专栏:后端知识体系后端知识体系

# 获取满足指数的最长字符串

字母表的26个字母,每个字母(忽略大小写)按照他们在字母表的顺序,代表一个数,例如:a代表1,h代表8,z代表26

对于任意由英文字母组成的字符串,我们可以把他们每一位对应的数加起来,便可以计算出这个字符串的指数,例如:abc的指数为6。

现在给你一个字符串与一个期望的指数,希望可以找出这个字符串的所有满足这个指数子串中,最长子串的长度。

要求:时间复杂度为O(n),空间复杂度为O(1)

输入描述:

代码语言:javascript
复制
输入为两行,第一行是字符串,第二行是期望的指数,例如:

bcdafga
8

输出描述:

代码语言:javascript
复制
输出为最长子串的长度。如果没有合适的子串,则应该返回0,例如,对于示例中的输入,应该输出:
3

# 解题思路

方法1、双指针:

初始化left和right指针,len指针记录最长子串的长度,res记录当前窗口内数值的和

采用类似滑动窗口的思想

  • 当[left,right)窗口内的值等于期望值时,说明找到了一个满足期望的子串,更新最长子串长度,因为此时窗口值已经等于期望值,向右扩展必定会使窗口值增加,所以此时应该缩减左窗口,才有可能在后续的子串中找到另外的满足期望值的left和right,res减去缩减左窗口的值,同时使得left++
  • 当[left,right)窗口内的值大于期望值时,需要缩减左窗口,即left++,同时时res减去左窗口的缩减部分的值
  • 当[left,right)窗口内的值小于期望值时,需要向右扩展窗口,即right++,同时res加上右窗口增加部分的值

# Java代码

代码语言:javascript
复制
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.nextLine().toCharArray();
        int exNum = Integer.parseInt(sc.nextLine().trim());
        int left = 0;
        int right = 0;
        int len = 0;
        int res = 0;
        while (right < s.length) {
            if (res == exNum) {
                len = Math.max(len, right - left);
                res -= (s[left] - 'a' + 1);
                left++;
            } else if (res > exNum) {
                res -= (s[left] - 'a' + 1);
                left++;
            } else {
                res += (s[right] - 'a' + 1);
                right++;
            }
        }
        System.out.println(len);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-08-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • # 获取满足指数的最长字符串
    • # 解题思路
      • # Java代码
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档