Java 中不重叠子字符串的最大数量

13 2025年5月 | 阅读 3 分钟

给定一个字符串 s，任务是找到可以提取的不重叠子串的最大数量，同时确保每个选定的子串都包含其出现的所有字符的每一个实例。以字典顺序返回子串列表。

示例 1

输入： "abbaccd"

输出： ["bb", "cc", "d"]

解释： "bb" 和 "cc" 是自包含子串，而 "d" 单独出现，最大化数量。

示例 2

输入： "adefaddaccc"

输出： ["e", "f", "ccc"]

解释： "e" 和 "f" 是孤立的，而 "ccc" 是一个有效的子串，因为所有的 'c' 都包含在其中。

方法 1：贪心与区间合并法

该方法解决了查找最大数量不重叠子串的问题，同时确保每个子串都是自包含的。

算法

步骤 1： 找到字符串中每个字符的第一个和最后一个出现位置。

步骤 2： 扩展每个字符的区间，以包含其范围内的所有字符。

步骤 3： 根据结束索引对区间进行排序。

步骤 4： 贪心地选择最大数量的不重叠区间，以形成最终的子串。

import java.util.*;
public class MaxNonOverlappingSubstrings {
    public List<String> maxNumOfSubstrings(String s) {
        int n = s.length();
        int[] first = new int[26], last = new int[26]; // Arrays to store first and last occurrence of each character
        Arrays.fill(first, -1);
        // Find first and last occurrence of each character
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (first[c - 'a'] == -1) first[c - 'a'] = i; // Store first occurrence
            last[c - 'a'] = i; // Store last occurrence
        }
        List<int[]> intervals = new ArrayList<>();
        //Expand each interval to cover all occurrences of characters inside it
        for (int i = 0; i < 26; i++) {
            if (first[i] == -1) continue; // Skip characters that are not in the string
            int left = first[i], right = last[i]; // Initial interval for character i
            boolean valid = true;
            // Expand the interval to include all necessary characters
            for (int j = left; j <= right; j++) {
                if (first[s.charAt(j) - 'a'] < left) { // If any character in this range extends before `left`
                    valid = false; // Invalid interval, skip it
                    break;
                }
                right = Math.max(right, last[s.charAt(j) - 'a']); // Expand the interval if needed
            }
            if (valid) intervals.add(new int[]{left, right}); // Store valid intervals
        }
        //Sort intervals by ending index
        intervals.sort(Comparator.comparingInt(a -> a[1]));
        // Greedily select non-overlapping intervals
        List<String> result = new ArrayList<>();
        int prevEnd = -1; // To track the end of the last selected interval
        for (int[] interval : intervals) {
            if (interval[0] > prevEnd) { // If current interval does not overlap with the previous one
                result.add(s.substring(interval[0], interval[1] + 1)); // Add substring to result
                prevEnd = interval[1]; // Update the last selected interval's end index
            }
        }
        return result;
    }
    public static void main(String[] args) {
        MaxNonOverlappingSubstrings obj = new MaxNonOverlappingSubstrings();
        System.out.println(obj.maxNumOfSubstrings("abbaccd")); 
    }
}   

输出

 
[bb, cc, d]

复杂度

时间复杂度： 程序的 O(n)。因为需要扫描字符串、扩展区间和选择不重叠的区间。

空间复杂度： 程序的 O(1)。因为我们使用固定大小的数组（26 个字符）并存储最多 26 个区间。

下一个主题Java 中的非原始数据类型

← 上一个下一个 →

Java 中不重叠子字符串的最大数量

方法 1：贪心与区间合并法

算法

复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中不重叠子字符串的最大数量

方法 1：贪心与区间合并法

算法

复杂度

相关帖子

Java 中的情侣牵手问题

最流行的 Java 后端工具

PermGen space Java

Queue 的 poll() 和 remove() 方法的区别

Java vs. JavaScript

Java 程序求最大乘积子数组

Instantiation in Java

Custom ArrayList in Java

CharsetDecoder unmappableCharacterAction() method in Java with Examples

Java 中洗牌数组

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器