首页
学习
活动
专区
圈层
工具
发布

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

# 获取满足指数的最长字符串 字母表的26个字母,每个字母(忽略大小写)按照他们在字母表的顺序,代表一个数,例如:a代表1,h代表8,z代表26 对于任意由英文字母组成的字符串,我们可以把他们每一位对应的数加起来...,便可以计算出这个字符串的指数,例如:abc的指数为6。...现在给你一个字符串与一个期望的指数,希望可以找出这个字符串的所有满足这个指数子串中,最长子串的长度。...要求:时间复杂度为O(n),空间复杂度为O(1) 输入描述: 输入为两行,第一行是字符串,第二行是期望的指数,例如: bcdafga 8 输出描述: 输出为最长子串的长度。...如果没有合适的子串,则应该返回0,例如,对于示例中的输入,应该输出: 3 # 解题思路 方法1、双指针: 初始化left和right指针,len指针记录最长子串的长度,res记录当前窗口内数值的和 采用类似滑动窗口的思想

94110

最长子字符串

题目 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。...输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。...输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。...//2、继续从第二个字符,重复1步骤,比较长度,留下最长的 //3、重复2,返回最长result public static int lengthOfLongestSubstring(String s)...而 Set 的大小取决于字符串 nn 的大小以及字符集 / 字母 mm 的大小。

80710
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    获取2个字符串的最长公共子串

    ,所以先要处理找两个字符串最长公共子串的问题。...程序源码 def getMaxCommonSubstr(s1, s2): # 求两个字符串的最长公共子串 # 思想:建立一个二维数组,保存连续位相同与否的状态 len_s1 = len(s1)...record = [[0 for i in range(len_s2+1)] for j in range(len_s1+1)] maxNum = 0 # 最长匹配长度...分析 对于测试字符串为: s1='abcdef' s2='bcxdef' 明显看出有2个公共子串,bc和def,上述的方法就是用2个字符串各自的长度建立了一个矩阵,矩阵数值初始都是0,一个字符一个字符的进行对比...假设字符串长度分别为n和m,则创建这个矩阵的时候,算法复杂度为O(nm),查找最大子串的算法复杂度为O(nm),整体算法的复杂度为2O(nm)。

    3.2K30

    脑子要烧坏了:使用manache算法查找最长回文子字符串

    所谓回文就是将字符串倒转后字符的排列与原来一样的字符串,例如”aba”。在回文问题中有一个特定类型,那就是从给定字符串中查找最长回文。...例如”efabababa”中最长回文子字符串就是从下标为2开始的字符串”abababa”,现在问题是给定字符串后,我们如何查找长度最长的回文子串呢。...有了上面办法后给定字符串我们就能查找最长回文子字符串,那就是我们依次遍历字符串中每个字符,然后以该字符作为中心点,然后利用上面描述方法判断以该点为中心的字符串能形成多长的回文,当遍历完所有字符后就能得到最长回文子字符串...,通常情况下我们使用’|’来作为辅助字符,于是字符串变成 |a|b|b|a|,于是中心字符就是下标为4的”|”,那么使用上面算法就能正确查找出字符串”|a|b|b|a|”是回文,然后把辅助字符去掉,剩下的字符串...,但通过输出结果可以很容易获取,我们只要从上面结构中拿到最大值,同时最大值在数组中的下标就对应回文字符串中心字符所在位置。

    1.1K20

    Day8-字符串-最长回文串

    一 唠唠 今天开始字符串的算法题 嗯,没了 ? 二 直接上题 Q:已知一个字符串,求该字符串中的字符可以生成的最长回文字符串的长度。...例如:s = “abccccddaa”,可生成的最长回文字符串的长度为9,如“dccaaaccd”,“adccbccda”,“acdcacdca”等都是正确的。...当然,不同的整数和字符串,经过哈希函数之后,可能映射到哈希表的同一个位置,就是下标,就会产生哈希冲突,比较经典的方法是,使用拉链法(映射到同一下标的元素,连接在同一个单链表中)解决冲突,在这就不赘述了,...所以对于该字符串,当c作为中心字符时,就需要丢掉一个d,当d作为中心字符时,就要丢掉一个c。比如“abdcccdba”,或“abcdddcba”都是最后的最长回文串。...int main(){ string s = "abccccdddaaaffggg"; int result = longestPalindrome(s); printf("该字符串的最长回文串长度为

    81310

    【字符串】最长回文子串 ( 蛮力算法 )

    文章目录 一、回文串、子串、子序列 二、最长回文子串 1、蛮力算法 2、时间复杂度最优方案 一、回文串、子串、子序列 ---- " 回文串 ( Palindrome ) " 是 正反都一样的字符串..., 前后顺序不允许颠倒 , 如 “ad” , “bd” , “acd” 等 ; ( 非连续字符 ) n 个字符串的子串个数是 2^n 个 ( 集合的子集数 ) ; 二、最长回文子串 ---- 问题链接...: https://www.lintcode.com/problem/200/description 给出一个字符串(假设长度最长为1000),求出它的最长回文子串,你可以假定只有一个满足条件的最长回文串...1、蛮力算法 蛮力算法 : ① 先获取所有的子串 ; 嵌套两层循环 , 外层循环起点索引 , 内层循环终点索引 , 将 \cfrac{n(n+1)}{2} +1 个子串都遍历出来 ; 该操作是 O...(n^2) 的算法复杂度 ; ② 验证子串是否是回文串 ; 使用 相向双指针算法 , 设置两个指针 , 左指针指向字符串开始位置 , 右指针指向字符串结束位置 , 对比左右指针是否相等 , 如果相等

    1.5K20
    领券