基于jsp的购物网站开发,合肥的房产网站建设,建设银行官方网站入口,免费友链互换文章目录1. 题目2. 解题1. 题目
给你一个只包含小写字母的字符串 s #xff0c;你需要找到 s 中最多数目的非空子字符串#xff0c;满足如下条件#xff1a;
这些字符串之间互不重叠#xff0c;也就是说对于任意两个子字符串 s[i…j] 和 s[k…l] #xff0c;要么 j …
文章目录1. 题目2. 解题1. 题目
给你一个只包含小写字母的字符串 s 你需要找到 s 中最多数目的非空子字符串满足如下条件
这些字符串之间互不重叠也就是说对于任意两个子字符串 s[i…j] 和 s[k…l] 要么 j k 要么 i l 。如果一个子字符串包含字符 char 那么 s 中所有 char 字符都应该在这个子字符串中。
请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。
请注意你可以以 任意 顺序返回最优解的子字符串。
示例 1
输入s adefaddaccc
输出[e,f,ccc]
解释下面为所有满足第二个条件的子字符串
[adefaddacccadefadda,ef,e,f,ccc,
]
如果我们选择第一个字符串那么我们无法再选择其他任何字符串所以答案为 1 。
如果我们选择 adefadda 剩下子字符串中我们只可以选择 ccc
它是唯一不重叠的子字符串所以答案为 2 。
同时我们可以发现选择 ef 不是最优的因为它可以被拆分成 2 个子字符串。
所以最优解是选择 [e,f,ccc] 答案为 3 。
不存在别的相同数目子字符串解。示例 2
输入s abbaccd
输出[d,bb,cc]
解释注意到解 [d,abba,cc] 答案也为 3 但它不是最优解因为它的总长度更长。提示
1 s.length 10^5
s 只包含小写英文字母。来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-substrings 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考大佬的思路
class Solution {
public:vectorstring maxNumOfSubstrings(string s) {vectorint start(26,-1), end(26,-1);int i 0, n s.size(), l, r, last -1;for(i 0; i n; i){char ch s[i];if(start[ch-a] -1)start[ch-a] i;end[ch-a] i;}vectorint endpos;for(auto e : end)if(e ! -1)endpos.push_back(e);sort(endpos.begin(), endpos.end());vectorstring ans;for(auto e : endpos){l start[s[e]-a];r e;while(l r){if(end[s[r]-a] e || l last)break;l min(l, start[s[r]-a]);r--;}if(r l){ans.push_back(s.substr(l, e-l1));last e;}}return ans;}
};184 ms 20 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
