Maximum Number of Non-Overlapping Substrings solution and explanation

def maxNumOfSubstrings(s):
    first, last = {}, {}
    for i, c in enumerate(s):
        if c not in first:
            first[c] = i
        last[c] = i
    
    intervals = []
    for i in range(len(s)):
        if i == first[s[i]]:
            end = last[s[i]]
            j = i
            while j <= end:
                end = max(end, last[s[j]])
                j += 1
            intervals.append((i, end))
            
    intervals.sort(key = lambda x: x[1])
    ans, prev_end = [], -1
    for i, j in intervals:
        if i > prev_end:
            ans.append(s[i:j+1])
            prev_end = j
    return ans

s = "adefaddaccc"
print(maxNumOfSubstrings(s))

import java.util.*;

public class MaxNonOverlap {
    public List<String> maxNumOfSubstrings(String s) {
        int[] start = new int[26];
        int[] end = new int[26];
        Arrays.fill(start, Integer.MAX_VALUE);
        Arrays.fill(end, Integer.MIN_VALUE);

        for (int i = 0; i < s.length(); 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<int[]> intervals = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (i == start[s.charAt(i) - 'a']) {
                int j = i;
                int right = end[s.charAt(i) - 'a'];
                while (j <= right) {
                    right = Math.max(right, end[s.charAt(j) - 'a']);
                    j++;
                }
                intervals.add(new int[]{i, right});
            }
        }

        intervals.sort((a, b) -> Integer.compare(a[1], b[1]));

        List<String> result = new ArrayList<>();
        int lastEnd = -1;
        for (int[] interval : intervals) {
            if (interval[0] > lastEnd) {
                result.add(s.substring(interval[0], interval[1] + 1));
                lastEnd = interval[1];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        MaxNonOverlap obj = new MaxNonOverlap();
        System.out.println(obj.maxNumOfSubstrings("adefaddaccc"));
    }
}

function maxNumOfSubstrings(s) {
    const n = s.length;
    const first = Array(26).fill(Infinity);
    const last = Array(26).fill(-Infinity);
    const codeA = 'a'.charCodeAt(0);

    for (let i = 0; i < n; i++) {
        const charIdx = s.charCodeAt(i) - codeA;
        if (first[charIdx] === Infinity) first[charIdx] = i;
        last[charIdx] = i;
    }

    const intervals = [];
    for (let i = 0; i < n; i++) {
        if (i === first[s.charCodeAt(i) - codeA]) {
            let j = i;
            let right = last[s.charCodeAt(i) - codeA];
            while (j <= right) {
                right = Math.max(right, last[s.charCodeAt(j) - codeA]);
                j++;
            }
            intervals.push([i, right]);
        }
    }

    intervals.sort((a, b) => a[1] - b[1]);

    const res = [];
    let lastEnd = -1;
    for (const [start, end] of intervals) {
        if (start > lastEnd) {
            res.push(s.substring(start, end + 1));
            lastEnd = end;
        }
    }

    return res;
}

const result = maxNumOfSubstrings("abbaccd");
console.log(result);

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return ((int*)a)[1] - ((int*)b)[1];
}

char** maxNumOfSubstrings(char* s, int* returnSize) {
    int len = strlen(s);
    int start[26];
    int end[26];
    for(int i = 0; i < 26; i++) {
        start[i] = len;
        end[i] = -1;
    }

    for(int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        start[c] = start[c] < i ? start[c] : i;
        end[c] = end[c] > i ? end[c] : i;
    }

    int intervals[len][2];
    int count = 0;
    for(int i = 0; i < len; i++) {
        if(i == start[s[i] - 'a']) {
            int j = i;
            int right = end[s[i] - 'a'];
            while(j <= right) {
                right = right > end[s[j] - 'a'] ? right : end[s[j] - 'a'];
                j++;
            }
            intervals[count][0] = i;
            intervals[count++][1] = right;
        }
    }

    qsort(intervals, count, sizeof(intervals[0]), compare);

    char** res = malloc(len * sizeof(char*));
    *returnSize = 0;
    int lastEnd = -1;
    for(int i = 0; i < count; i++) {
        if(intervals[i][0] > lastEnd) {
            int length = intervals[i][1] - intervals[i][0] + 1;
            res[*returnSize] = malloc((length+1) * sizeof(char));
            strncpy(res[*returnSize], s + intervals[i][0], length);
            res[*returnSize][length] = '\0';
            (*returnSize)++;
            lastEnd = intervals[i][1];
        }
    }

    return res;
}

int main() {
    int returnSize;
    char s[] = "abbaccd";
    char** result = maxNumOfSubstrings(s, &returnSize);
    printf("Output: [");
    for(int i = 0; i < returnSize; i++) {
        printf("%s%s", result[i], (i == returnSize - 1) ? "" : ", ");
        free(result[i]);
    }
    printf("]\n");
    free(result);
}