Leetcode每日一题 —— 1520. 最多的不重叠子字符串

魔法师 2026-09-18 09:51 1

思路

朴素思路

先从左到右、从右到左分别遍历一遍，记录每种字母出现的第一个、最后一个和中间夹杂的其他字母。

遍历26个字母，如果字母的范围内夹杂了其他字母，那么更新范围，直到不再变动位置。

按范围从小到大排序并遍历，取与之前选中字符串不重叠的字符串加入到结果中。

PS

朴素、低效且丑陋

代码

class Solution {

    public List<String> maxNumOfSubstrings(String s) {

        int[] chars = new int[s.length()];

        for (int i = 0; i < chars.length; i++) {

            chars[i] = s.charAt(i) - 'a';

        }

        int[] first = new int[26];

        int[] last = new int[26];

        HashSet<Integer>[] sets = new HashSet[26];

        Arrays.fill(first, -1);

        Arrays.fill(last, -1);

        for (int i = 0; i < 26; i++) {

            sets[i] = new HashSet<>();

        }

        for (int i = chars.length - 1; i>= 0; i--) {

            if (last[chars[i]] == -1) {

                last[chars[i]] = i;

            }

        }

        for (int i = 0; i < chars.length; i++) {

            if (first[chars[i]] == -1) {

                first[chars[i]] = i;

            }

            for (int j = 0; j < 26; j++) {

                if (first[j] != -1 && last[j] > i) {

                    sets[j].add(chars[i]);

                }

            }

        }

        boolean changed = false;

        do {

            changed = false;

            for (int i = 0; i < 26; i++) {

                for (Integer j : sets[i]) {

                    if (first[i] > first[j]) {

                        first[i] = first[j];

                        changed = true;

                    }

                    if (last[i] < last[j]) {

                        last[i] = last[j];

                        changed = true;

                    }

                }

            }

        } while (changed);

        List<int[]> rec = new ArrayList<>();

        for (int i = 0; i < 26; i++) {

            if (first[i] != -1) {

                rec.add(new int[]{last[i] - first[i] + 1, first[i], last[i]});

            }

        }

        rec.sort((a, b) -> a[0] - b[0]);

        boolean[] vis = new boolean[rec.size()];

        for (int i = 0; i < rec.size(); i++) {

            int[] r = rec.get(i);

            boolean v = true;

            for (int j = 0; j < i; j++) {

                if (!vis[j]) {

                    continue;

                }

                int[] t = rec.get(j);

                if (r[1] <= t[1] && r[2] >= t[1]) {

                    v = false;

                    break;

                }

            }

            if (v) {

                vis[i] = true;

            }

        }

        List<String> result = new ArrayList<>();

        for (int i = 0; i < vis.length; i++) {

            if (vis[i]) {

                int[] r = rec.get(i);

                result.add(s.substring(r[1], r[2] + 1));

            }

        }

        return result;

    }

}

最新回复 (3)

SomeBottle 09-18 10:14

1楼

有点丑陋了。思路还是比较明确的，找每个字符首次 (l) 和最后出现 (r) 的位置，其之间出现的字符 \alpha 可能全出现在 (l, r)、也可能最早出现在 l 之前、亦可能最晚出现在 r 之后。

\alpha 出现在 r 之后，根据题目要求需要扩展 r；但 \alpha 出现在 l 之前的话，不用管当前区间，因为处理到该字符的时候就会考虑到当前这个区间。

扩展出区间后，按贪心思路，选择最早结束的、没有发生交叠的区间即可。

class Solution {

public:

    vector<string> maxNumOfSubstrings(string s) {

        // 也就是说子字符串中包含的字符都应该只出现在这个子字符串中

        // 一个字符如果后面还会出现，其两次出现之间可能有更短的子字符串，也可能牵涉有字符在后面还会出现

        vector<vector<int>> ap(26,vector<int>(2,-1)); // 存每个字符首次和最后出现的位置

        for(int i=0;i<s.size();i++){

            if(ap[s[i]-'a'][0]==-1){

                ap[s[i]-'a'][0]=i;

            }

            ap[s[i]-'a'][1]=i;

        }

        // 检查每个字符对应的子字符串范围

        vector<pair<int,int>> intvs; // 存合法的子字符串范围区间 <r, l>，先存 r 是为了方便排序

        for(int i=0;i<26;i++){

            if(ap[i][0]==-1){

                // 不存在该字母

                continue;

            }

            int l=ap[i][0],r=ap[i][1];

            bool skip=false;

            for(int j=l;j<=r;j++){

                // 出现在之间的字符，如果其最早出现在 l 之前，说明当前区间和之前的交叠了，出现在之前的字符涉及的子字符串包含了当前区间，可以跳过

                if(ap[s[j]-'a'][0]<l){

                    skip=true;

                    break;

                }

                // 出现在之间的字符，可能在当前字符最后出现之后还有出现

                // 为了让子字符串包含的字符只出现在子字符串中

                // 扩展右边界

                r=max(r,ap[s[j]-'a'][1]);

            }

            if(skip){

                continue;

            }

            intvs.emplace_back(r,l);

        }

        // 按右端排序

        sort(intvs.begin(),intvs.end());

        // 扫描选择出不重叠的子字符串

        int lastR=-1;

        vector<string> res;

        for(auto& p:intvs){

            if(p.second<lastR){

                // 当前区间开始点小于上个区间结束点，有重叠

                continue;

            }

            lastR=p.first;

            res.emplace_back(s.substr(p.second,p.first-p.second+1));

        }

        return res;

    }

};

rainnguy 09-18 10:40

2楼

好久没做了，以后每天争取来做一题

CPython 09-18 12:01

3楼

看见hard就不想做,无法战胜.

13. 罗马数字转整数 - 力扣（LeetCode）

f = {

    'I': 1,

    'V': 5,

    'X': 10,

    'L': 50,

    'C': 100,

    'D': 500,

    'M': 1000,

}



class Solution:

    def romanToInt(self, s: str) -> int:

        ans = 0

        for x, y in pairwise(s):

            x, y = f[x], f[y]

            ans += x if x >= y else -x 

        return ans + f[s[-1]]

* 帖子来源Linux.do

附近帖子

↑OpenCodeZen的免费档更加收紧了虽然能绕过去，不过好像没啥折腾的意义了
↑佬们求推荐个笔记本品牌~
↑想问一下哪里还有纯正的img2.0可以用
↑bybit注册问题
↑gpt-6 pro 和 Fable 5.1 max 感觉做科研还是不行啊
📍 Leetcode每日一题 —— 1520. 最多的不重叠子字符串
↓瑞幸WorkBuddy积分抽奖
↓【恶臭】Qoder的免费鸡蛋都是臭蛋，大家别上当了
↓哈基米3.8flash变得好慢，是不是有大的要来了
↓今天科创50还会演戏一天么2026918
↓求助，codex更新后在旧会话里发不了消息