Java

  • import java.util.ArrayList;
    import java.util.List;
    
    /**
    
     A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
    
     Example 1:
     Input: S = "ababcbacadefegdehijhklij"
     Output: [9,7,8]
     Explanation:
     The partition is "ababcbaca", "defegde", "hijhklij".
     This is a partition so that each letter appears in at most one part.
     A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
     Note:
    
     S will have length in range [1, 500].
     S will consist of lowercase letters ('a' to 'z') only.
    
     */
    
    public class Partition_Labels {
    
        class Solution {
            public List<Integer> partitionLabels(String s) {
    
                List<Integer> result = new ArrayList<>();
    
                if (s == null || s.length() == 0) {
                    return result;
                }
    
                int[] lastSeenAt = new int[256];
                for (int i = 0; i < s.length(); i++) {
                    lastSeenAt[s.charAt(i) - 'a'] = i;
                }
    
                int j = 0;
                int anchor = 0;
                for (int i = 0; i < s.length(); i++) {
                    j = Math.max(j, lastSeenAt[s.charAt(i) - 'a']);
    
                    if (i == j) {
                        result.add(j - anchor + 1);
                        anchor = j + 1;
                    }
                }
    
                return result;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/partition-labels/
    // Time: O(S)
    // Space: O(1)
    class Solution {
    public:
        vector<int> partitionLabels(string s) {
            int N = s.size(), last[26] = {};
            memset(last, -1, sizeof(last));
            for (int i = 0; i < N; ++i) last[s[i] - 'a'] = i;
            vector<int> ans;
            for (int i = 0; i < N;) {
                int start = i;
                for (int end = i + 1; i < end; ++i) end = max(end, last[s[i] - 'a'] + 1);
                ans.push_back(i - start);
            }
            return ans;
        }
    };
    
  • class Solution(object):
        def partitionLabels(self, S):
            """
            :type S: str
            :rtype: List[int]
            """
            lindex = {c: i for i, c in enumerate(S)}
            j = anchor = 0
            ans = []
            for i, c in enumerate(S):
                j = max(j, lindex[c])
                if i == j:
                    ans.append(j - anchor + 1)
                    anchor = j + 1
            return ans
    

Java

  • class Solution {
        public List<Integer> partitionLabels(String S) {
            int[] endArray = new int[26];
            Arrays.fill(endArray, -1);
            int length = S.length();
            for (int i = 0; i < length; i++) {
                char c = S.charAt(i);
                int letterIndex = c - 'a';
                endArray[letterIndex] = i;
            }
            List<Integer> partition = new ArrayList<Integer>();
            int start = 0, end = 0;
            for (int i = 0; i < length; i++) {
                char c = S.charAt(i);
                int letterIndex = c - 'a';
                int curEnd = endArray[letterIndex];
                end = Math.max(end, curEnd);
                if (i == end) {
                    partition.add(end - start + 1);
                    start = i + 1;
                }
            }
            return partition;
        }
    }
    
  • // OJ: https://leetcode.com/problems/partition-labels/
    // Time: O(S)
    // Space: O(1)
    class Solution {
    public:
        vector<int> partitionLabels(string s) {
            int N = s.size(), last[26] = {};
            memset(last, -1, sizeof(last));
            for (int i = 0; i < N; ++i) last[s[i] - 'a'] = i;
            vector<int> ans;
            for (int i = 0; i < N;) {
                int start = i;
                for (int end = i + 1; i < end; ++i) end = max(end, last[s[i] - 'a'] + 1);
                ans.push_back(i - start);
            }
            return ans;
        }
    };
    
  • class Solution(object):
        def partitionLabels(self, S):
            """
            :type S: str
            :rtype: List[int]
            """
            lindex = {c: i for i, c in enumerate(S)}
            j = anchor = 0
            ans = []
            for i, c in enumerate(S):
                j = max(j, lindex[c])
                if i == j:
                    ans.append(j - anchor + 1)
                    anchor = j + 1
            return ans
    

All Problems

All Solutions