Partition Labels


  • 0

    Click here to see the full article post


  • 0

    Ruby Solution:

    @param {String} s

    @return {Integer[]}

    def partition_labels(s)
    set = Set.new
    subs = []
    index = 0
    length = 0
    lastLength = 0
    s.each_char do |c|
    if !set.include?(c)
    set.add(c)
    lastIndex = s.rindex(c)
    length = lastIndex + 1 if lastIndex > length - 1
    end
    if index == length - 1
    subs.push(length - lastLength)
    lastLength = length
    length = 0
    end
    index += 1
    end
    subs
    end


  • 0
    # @param {String} s
    # @return {Integer[]}
    def partition_labels(s)
        set = Set.new
        subs = []
        index = 0
        length = 0
        lastLength = 0
        s.each_char do |c|
            if !set.include?(c)
                set.add(c)
                lastIndex = s.rindex(c)
                length = lastIndex + 1 if lastIndex > length - 1
            end
            if index == length - 1
                subs.push(length - lastLength)
                lastLength = length
                length = 0
            end
            index += 1
        end
        subs
    end
    

  • 0
    W

    How about an approach using intervals. Compute interval (start, end) for each letter [a-z] , where start is first occurrence of letter, and end is last occurrence of letter. Then we merge any overlapping intervals, and the resulting intervals can form the answer.


  • 0
    B

    Is the solution using constant space which is O(1)?


  • 0
    T

    My java solution 29ms

    import java.util.Hashtable;
    class Solution {
        public List<Integer> partitionLabels(String S) {
            if(S.isEmpty())
                return null;
            List<Integer> result = new ArrayList<Integer>();
            
            Hashtable<Character, Integer> lastindex= new Hashtable<Character, Integer>();
            
            for(int i=0;i<S.length();i++)
            {
                if(!lastindex.containsKey(S.charAt(i)))
                {
                    lastindex.put(S.charAt(i),i);
                }
                else
                {
                    lastindex.put(S.charAt(i),i);
                }
            }
            int start = 0;
            int end =0;
            for(int i=start;i<S.length();i++)
            {
                end = Math.max(end,lastindex.get(S.charAt(i)));
                if(i==end)
                {
                    result.add(end+1-start);
                    start = end+1;
                }
            }
            
            return result;
        }
    }
    

  • 0

    My C++ solution 14ms, 9lines

    vector<int> partitionLabels(string S) {
            vector<int> ans;
            for (int i = 0, start = 0, end = 0; i < S.length(); i++) {
                end = max(end, (int)S.find_last_of(S[i]));
                if (i == end) {
                    ans.push_back(end - start + 1);
                    start = end + 1;
                }
            }
            return ans;
        }
    

  • 0
    G

    Wouldn't the time complexity of the Approach #1 be O(n^2)?

    It seems to me like in the first letter it checks the whole string minus the first char to find the last occurrence, then in the second letter the whole string - first 2 chars, and so on. (n - 1) + (n - 2) + ... + 1 is an arithmetic progression and the sum is O(n^2).


  • 0
    G

    Ah ops nvm. Misunderstood how it found the last occurrence.


  • 0
    T

    @liuchuo Less lines does not mean less time =p You made repetitive calls to find_last_of, and that could be better cached (as the proposed solution does though). This gave me 7ms:

    vector<int> partitionLabels(string S) {
        vector<int> partitions;
        int last['z'-'a'+1];
       
        for (int i = 0; i < S.size(); ++i)
            last[S[i] - 'a'] = i;
        
        for (int i = 0, size = 1, end = 0; i < S.size(); ++i, ++size) {
            end = max(end, last[S[i] - 'a']);
            if (i == end) {
                partitions.push_back(size);
                size = 0;
            }
        }
        
        return partitions;
    }
    

  • 0
    N

    is it constant space?


  • 0
    A

    Space Complexity is O(n) if we consider that we have to return the size of the partitions in 'ans'. 'ans' would be O(n) in size in worst case.


  • 0

    I thought of this as Overlapping intervals and found the answer. Here, start of the interval is first occurrence of character and end is the last occurrence.

    class Ele{
        int start,end;
        char x;
        Ele(char ch,int s,int e){
            x = ch;
            start = s;
            end = e;
        }
    }
    public class Solution {
        public List<Integer> partitionLabels(String S) {
            List<Integer> res = new ArrayList<>();
            List<Ele> letters = new ArrayList<>(); 
            int[] l = new int[26];
            Arrays.fill(l,-1);
            int len = S.length();
            
            for(int i=0;i<len;++i){
                if(l[S.charAt(i)-'a'] == -1){
                    l[S.charAt(i)-'a'] = letters.size();
                    letters.add(new Ele(S.charAt(i),i,i));
                }else{
                    letters.get(l[S.charAt(i)-'a']).end = i;
                }
            }
            
            Collections.sort(letters,new Comparator<Ele>(){
                public int compare(Ele e1,Ele e2){
                    if(e1.start < e2.start) return -1;
                    if(e1.start > e2.start) return 1;
                    if(e1.end < e2.end) return -1;
                    if(e1.end > e2.end) return 1;
                    return 0;
                }
            });
            
            
            int start = letters.get(0).start,end = letters.get(0).end;
            int size = letters.size();
                    
            for(int i=1;i<size;++i){
                Ele t = letters.get(i);   
                if(t.start < end) end = Math.max(end,t.end);
                else{
                    res.add(end-start + 1);
                    start = t.start;
                    end = t.end;
                }
            }
            
            res.add(end-start+1);
            
            
            return res;
        }
    }
    

  • 0
    Z
        List<Integer> out = new ArrayList<>();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0; i<S.length(); i++) {
            map.put(S.charAt(i), i);            
        }
        Integer end=0, begin=0;
        System.out.print(map);
        for (int i=0; i<S.length(); i++) {
            Integer index = map.get(S.charAt(i));
            if (index.intValue() > end.intValue()) {
                end = index;
            } 
            if(i == end.intValue()) {
                out.add(end.intValue() - begin.intValue() + 1);
                begin = i + 1;
            }
        }
        return out;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.