文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個只包含小寫字母的字符串 s ，你需要找到 s 中最多數目的非空子字符串，滿足如下條件：

• 這些字符串之間互不重疊，也就是說對于任意兩個子字符串 s[i…j] 和 s[k…l] ，要么 j < k 要么 i > l 。
• 如果一個子字符串包含字符 char ，那么 s 中所有 char 字符都應該在這個子字符串中。

請你找到滿足上述條件的最多子字符串數目。如果有多個解法有相同的子字符串數目，請返回這些子字符串總長度最小的一個解。可以證明最小總長度解是唯一的。

請注意，你可以以 任意 順序返回最優解的子字符串。

示例 1： 輸入：s = "adefaddaccc" 輸出：["e","f","ccc"] 解釋：下面為所有滿足第二個條件的子字符串： ["adefaddaccc""adefadda","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:vector<string> maxNumOfSubstrings(string s) {vector<int> 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;}vector<int> endpos;for(auto e : end)if(e != -1)endpos.push_back(e);sort(endpos.begin(), endpos.end());vector<string> 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-l+1));last = e;}}return ans;} };

184 ms 20 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1520. 最多的不重叠子字符串（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。