# 1520. Maximum Number of Non-Overlapping Substrings

• Time: $O(26n) = O(n)$
• Space: $|\texttt{ans}|$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public: vector maxNumOfSubstrings(string s) { const int n = s.length(); vector ans; vector leftmost(26, n); // Leftmost index of each letter vector rightmost(26, -1); // Rightmost index of each letter for (int i = 0; i < n; ++i) { leftmost[s[i] - 'a'] = min(leftmost[s[i] - 'a'], i); rightmost[s[i] - 'a'] = i; } auto getNewRight = [&](int i) { int right = rightmost[s[i] - 'a']; for (int j = i; j <= right; ++j) { if (leftmost[s[j] - 'a'] < i) // Find a letter's first index < i return -1; right = max(right, rightmost[s[j] - 'a']); // Right expands dynamically } return right; }; int right = -1; // Last substring's rightmost index for (int i = 0; i < n; ++i) { if (i == leftmost[s[i] - 'a']) { // Current index is the first appearance const int newRight = getNewRight(i); if (newRight == -1) continue; // Find a letter's first index < i if (i <= right && !ans.empty()) ans.back() = s.substr(i, newRight - i + 1); else ans.push_back(s.substr(i, newRight - i + 1)); right = newRight; } } return ans; } };