LeetCode 763. Partition Labels

Posted on | In |

题目大意：把字符串分割成尽量多的不重叠子串，输出子串的长度数组。要求相同字符只能出现在一个子串中。
Problem:

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.

贪心 尽可能扩充区间

Solution 1: Greedy

Time complexity: O(n)

Space complexity: O(26/128)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> partitionLabels(string S) {
    //vector<int> arr(128,0);
        int arr[128];
	int start=0,end=0;
	vector<int> ans;
	for(int i=0;i<S.length();i++)
	arr[S[i]]=i;
	for(int i=0;i<S.length();i++){
		end=max(end,arr[S[i]]);
		if(i==end){
			ans.push_back(end-start+1);
            start=end+1;
		}
	}
       return ans; 
    }
};