# Partition Labels

• Ruby Solution:

# @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)
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

• ``````# @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)
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
``````

• 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.

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

• 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)
{
start = end+1;
}
}

return result;
}
}
``````

• 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;
}
``````

• 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).

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

• @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;
}
``````

• is it constant space?

• 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.

• 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();
}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{
start = t.start;
end = t.end;
}
}

return res;
}
}
``````

• ``````    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()) {