1520. Maximum Number of Non-Overlapping Substrings

class Solution {
    public List<String> maxNumOfSubstrings(String s) {
        int n = s.length();
        int[] first = new int[26];
        int[] last  = new int[26];
        Arrays.fill(first, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            first[c] = Math.min(first[c], i);
            last[c]  = Math.max(last[c],  i);
        }
        List<String> result = new ArrayList<>();
        int prevEnd = -1;
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            if (first[c] != i) continue;
            int l = i;
            int r = last[c];
            boolean valid = true;
            for (int j = l; j <= r; j++) {
                int ch = s.charAt(j) - 'a';
                if (first[ch] < l) {
                    valid = false;
                    break;
                }
                r = Math.max(r, last[ch]); // expand window
            }
            if (!valid) continue;
            if (l > prevEnd) {
                result.add(s.substring(l, r + 1));
                prevEnd = r;
            } else if (r < prevEnd) {
                result.set(result.size() - 1, s.substring(l, r + 1));
                prevEnd = r;
            }
        }
        
        return result;
    }
}

class Solution:
    def maxNumOfSubstrings(self, s):
        n = len(s)

        first = [n] * 26
        last = [-1] * 26

        for i in range(n):
            c = ord(s[i]) - ord('a')
            first[c] = min(first[c], i)
            last[c] = max(last[c], i)

        result = []
        prevEnd = -1

        for i in range(n):
            c = ord(s[i]) - ord('a')

            if first[c] != i:
                continue

            l = i
            r = last[c]
            valid = True

            for j in range(l, r + 1):
                ch = ord(s[j]) - ord('a')

                if first[ch] < l:
                    valid = False
                    break

                r = max(r, last[ch])

            if not valid:
                continue

            if l > prevEnd:
                result.append(s[l:r + 1])
                prevEnd = r

            elif r < prevEnd:
                result[-1] = s[l:r + 1]
                prevEnd = r

        return result

class Solution {
public:
    vector<string> maxNumOfSubstrings(string s) {
        int n = s.length();

        vector<int> first(26, n);
        vector<int> last(26, -1);

        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';

            first[c] = min(first[c], i);
            last[c] = max(last[c], i);
        }

        vector<string> result;
        int prevEnd = -1;

        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';

            if (first[c] != i)
                continue;

            int l = i;
            int r = last[c];
            bool valid = true;

            for (int j = l; j <= r; j++) {
                int ch = s[j] - 'a';

                if (first[ch] < l) {
                    valid = false;
                    break;
                }

                r = max(r, last[ch]);
            }

            if (!valid)
                continue;

            if (l > prevEnd) {
                result.push_back(s.substr(l, r - l + 1));
                prevEnd = r;
            }
            else if (r < prevEnd) {
                result.back() = s.substr(l, r - l + 1);
                prevEnd = r;
            }
        }

        return result;
    }
};

class Solution {
    maxNumOfSubstrings(s) {
        const n = s.length;

        const first = Array(26).fill(n);
        const last = Array(26).fill(-1);

        for (let i = 0; i < n; i++) {
            const c = s.charCodeAt(i) - 97;

            first[c] = Math.min(first[c], i);
            last[c] = Math.max(last[c], i);
        }

        const result = [];
        let prevEnd = -1;

        for (let i = 0; i < n; i++) {
            const c = s.charCodeAt(i) - 97;

            if (first[c] !== i) {
                continue;
            }

            let l = i;
            let r = last[c];
            let valid = true;

            for (let j = l; j <= r; j++) {
                const ch = s.charCodeAt(j) - 97;

                if (first[ch] < l) {
                    valid = false;
                    break;
                }

                r = Math.max(r, last[ch]);
            }

            if (!valid) {
                continue;
            }

            if (l > prevEnd) {
                result.push(s.substring(l, r + 1));
                prevEnd = r;
            }
            else if (r < prevEnd) {
                result[result.length - 1] = s.substring(l, r + 1);
                prevEnd = r;
            }
        }

        return result;
    }
}