# 763. Partition Labels

• Time: $O(n)$
• Space: $O(128) = O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: vector partitionLabels(string s) { vector ans; vector rightmost(128); for (int i = 0; i < s.length(); ++i) rightmost[s[i]] = i; int l = 0; // First index of current running string int r = 0; // Right most so far for (int i = 0; i < s.length(); ++i) { r = max(r, rightmost[s[i]]); if (r == i) { ans.push_back(i - l + 1); l = i + 1; } } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public List partitionLabels(String s) { List ans = new ArrayList<>(); int[] rightmost = new int[128]; for (int i = 0; i < s.length(); ++i) rightmost[s.charAt(i)] = i; int l = 0; // First index of current running string int r = 0; // Right most so far for (int i = 0; i < s.length(); ++i) { r = Math.max(r, rightmost[s.charAt(i)]); if (r == i) { ans.add(i - l + 1); l = i + 1; } } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def partitionLabels(self, s: str) -> List[int]: ans = [] letterToRightmostIndex = {c: i for i, c in enumerate(s)} l = 0 r = 0 for i, c in enumerate(s): r = max(r, letterToRightmostIndex[c]) if i == r: ans.append(r - l + 1) l = r + 1 return ans