最多的不重叠子字符串

/*
 * 题目思路：
 * 1. 遍历字符串，记录每个字符第一次和最后一次出现的位置。
 * 2. 使用贪心算法，依次选择每个子字符串，使得每个字符只出现在一个子字符串中。
 * 3. 记录选择的子字符串，返回最终结果。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public List<String> maxNumOfSubstrings(String s) {
        int n = s.length();
        int[] start = new int[26];
        int[] end = new int[26];
        IntStream.range(0, 26).forEach(i -> {
            start[i] = n;
            end[i] = -1;
        });
        IntStream.range(0, n).forEach(i -> {
            char c = s.charAt(i);
            start[c - 'a'] = Math.min(start[c - 'a'], i);
            end[c - 'a'] = Math.max(end[c - 'a'], i);
        });

        List<String> res = new ArrayList<>();
        int[] right = {-1};
        IntStream.range(0, n).forEach(i -> {
            if (i == start[s.charAt(i) - 'a']) {
                int newRight = expand(s, i, end);
                if (newRight != -1) {
                    res.add(s.substring(i, newRight + 1));
                    right[0] = newRight;
                }
            }
            if (i == right[0]) {
                right[0] = -1;
            }
        });
        return res;
    }

    private int expand(String s, int i, int[] end) {
        int right = end[s.charAt(i) - 'a'];
        for (int j = i; j <= right; j++) {
            if (end[s.charAt(j) - 'a'] > right) {
                return -1;
            }
        }
        return right;
    }
}