江西企业网站建设电话,html5网站开发需要框架吗,牡丹江百度推广,小程序定制开发注意事项删除字符串两端相同字符后的最短长度
难度#xff1a;中等
给你一个只包含字符 a#xff0c;b 和 c 的字符串 s #xff0c;你可以执行下面这个操作#xff08;5 个步骤#xff09;任意次#xff1a;
选择字符串 s 一个 非空 的前缀#xff0c;这个前缀的所有字符都相…删除字符串两端相同字符后的最短长度
难度中等
给你一个只包含字符 ab 和 c 的字符串 s 你可以执行下面这个操作5 个步骤任意次
选择字符串 s 一个 非空 的前缀这个前缀的所有字符都相同。选择字符串 s 一个 非空 的后缀这个后缀的所有字符都相同。前缀和后缀在字符串中任意位置都不能有交集。前缀和后缀包含的所有字符都要相同。同时删除前缀和后缀。
请你返回对字符串 s 执行上面操作任意次以后可能 0 次能得到的 最短长度 。
双指针
思路
题目要求删除字符串 sss 中字母相同且不相交的前缀与后缀假设当前字符串的长度为 nnn则执行的删除规则如下
选择字符串 sss 一个非空的前缀 prefixs[0,⋯,l]\textit{prefix} s[0,\cdots,l]prefixs[0,⋯,l]这个前缀的所有字符都相同s[0]s[1]⋯s[l]s[0] s[1] \cdots s[l]s[0]s[1]⋯s[l]。选择字符串 sss 一个非空11的后缀 suffixs[r,⋯,n−1]\textit{suffix} s[r,\cdots,n-1]suffixs[r,⋯,n−1]这个后缀的所有字符都相同s[r]s[r1]⋯s[n−1]s[r] s[r 1] \cdots s[n-1]s[r]s[r1]⋯s[n−1]。前缀和后缀在字符串中任意位置都不能有交集即 lrl rlr。前缀和后缀包含的所有字符都要相同s[0]s[1]⋯s[l]s[r]s[r1]⋯s[n−1]s[0] s[1] \cdots s[l] s[r] s[r 1] \cdots s[n-1]s[0]s[1]⋯s[l]s[r]s[r1]⋯s[n−1]。同时删除前缀和后缀。
通过观察我们对 sss 进行分类讨论如下
sss 的长度为 111 时假设 s“as \text{a}s“a此时按照题目的删除规则此时不能删除。sss 的长度大于 111 且 sss 中的所有字符均相同假设 s“aaaas \text{aaaa}s“aaaa此时按照题目的删除规则 sss 一定可以全部删除完。sss 的长度大于 111 且 sss 存在字母相同的前缀与后缀假设 s“aaabbbcccas \text{aaabbbccca}s“aaabbbccca此时按照题目的删除规则最优选择是 sss 应当将前缀与后缀中连续的 ‘a’\text{a’}‘a’ 全部删除完删除完成后 s′“bbbcccs \text{bbbccc}s′“bbbccc。sss 的长度大于 111 且 sss 不存在字母相同的前缀与后缀假设 s“aaacccs \text{aaaccc}s“aaaccc此时按照删除规则无法进行删除。
根据以上的删除规则分类我们设 left\textit{left}left 和 right\textit{right}right 分别指向当前待删除字符串的起始位置与结束位置然后按照规则进行删除当前可以删除的条件必须满足如下:
只有字符串的长度大于 111 时我们才进行删除因此可以进行删除的条件一定需要满足 leftright\textit{left} \textit{right}leftright只有存在字母相同的前缀与后缀我们才进行删除因此可以进行删除的条件一定需要满足 s[left]s[right]s[\textit{left}] s[\textit{right}]s[left]s[right]。
假设有可以进行删除的前缀和后缀时则我们将所有字母相同的前缀与后缀全部删除此时 left\textit{left}left 需要向右移动right\textit{right}right 需要向左移动并删除字符串中字母相同的前缀与后缀直到无法删除为止。最终 left\textit{left}left 指向删除后字符串的左起点right\textit{right}right 指向删除后字符串的右终点剩余的字符串的长度则为 right−left1\textit{right} - \textit{left} 1right−left1。
需要注意的是如果当 sss 的长度大于 111 且 sss 中的字符全部相等时此时需要将 sss 全部进行删除则会出现 rightleft−1\textit{right} \textit{left} - 1rightleft−1。
复杂度分析
时间复杂度 O(n)O(n)O(n)其中 nnn 表示字符串的长度。我们只需遍历一遍字符串即可。空间复杂度 O(1)O(1)O(1)。
class Solution:def minimumLength(self, s: str) - int:l, r 0, len(s) - 1while r - l 1 and s[l] s[r]:now s[l]while l r and s[l] now:l 1while l r and s[r] now:r - 1return r - l 1来源力扣LeetCode 链接https://leetcode.cn/problems/minimum-length-of-string-after-deleting-similar-ends/
