# 763. Partition Labels

## LWC 67: 763. Partition Labels

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.

Note:

• S will have length in range [1, 500].
• S will consist of lowercase letters (‘a’ to ‘z’) only.

```    public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
if (S.length() == 0) return ans;

char[] cs = S.toCharArray();
StringBuilder sb = new StringBuilder();
int i = 0;
for (; i < cs.length; ++i) {
sb.append(cs[i]);
if (part(sb, i, S)) {
break;
}
}

List<Integer> sub = partitionLabels(S.substring(i + 1));
for (int hello : sub) ans.add(hello);
return ans;
}

public boolean part(StringBuilder sb, int i, String S) {
if (sb.toString().isEmpty()) return false;
for (int j = i + 1; j < S.length(); ++j) {
String letter = S.substring(j, j + 1);
if (sb.toString().contains(letter)) return false;
}
return true;
}```

```    public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
char[] cs = S.toCharArray();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < cs.length; ++i) {
sb.append(cs[i]);
if (part(sb, i, S)) {
sb = new StringBuilder();
}
}
return ans;
}

public boolean part(StringBuilder sb, int i, String S) {
if (sb.toString().isEmpty()) return false;
for (int j = i + 1; j < S.length(); ++j) {
String letter = S.substring(j, j + 1);
if (sb.toString().contains(letter)) return false;
}
return true;
}```

Java版本：

```    public List<Integer> partitionLabels(String S) {
List<Integer> ans = new ArrayList<>();
char[] cs  = S.toCharArray();
int n = cs.length;
int[] last = new int[32];
for (int i = 0; i < n; ++i) {
last[cs[i] - 'a'] = i;
}
int pre = -1;
int max = 0;
for (int i = 0; i < n; ++i) {
if (last[cs[i] - 'a'] > max) max = last[cs[i] - 'a'];
if (max == i) {
pre = max;
max = max + 1;
}
}
return ans;
}```

Python版本：

```class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
lst = {}
n = len(S)
for i, c in enumerate(S):
lst[c] = i
ans = []
max = 0
pre = -1
for i in range(n):
if lst[S[i]] > max: max = lst[S[i]]
if max == i:
ans.append(max - pre)
pre = max
max = max + 1
return ans```

0 条评论

• ### 4.6平面上的分治法（2）

指出一点：新的点一定由这些坐标的横纵坐标生成，所以求出投影即能满足条件①，条件②在求解①的过程中自然满足。

• ### LeetCode Weekly Contest 29解题思路

代码很简单，简单说明下思路就出来了。按照题意，不管怎么二分，整个数组都会被划分成两部分和，这两部分和必然一大一小。如nums = [1,4,3,2]，划分如下[...

• ### 3259. Wormholes

重新回顾了下Bellman-Ford算法，核心思路如下：从单个源点出发，如果经过N轮还在更新时，说明存在负环。证明：假设不存在负环，那么最短路径必然不会经过一个...

• ### POJ1041

欧拉路问题 本次比赛的水题 对于这题的无向图，要每一个点的度数都为偶数，才存在欧拉回路。 #include<iostream> #include<cstdi...

• ### 贪心算法举例分析

版权声明：本文为博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。

• ### LeetCode 914. 卡牌分组（最大公约数）

每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

• ### LeetCode Single Number题目分析代码

Given an array of integers, every element appears twice except for one. Find tha...

• ### LightOJ - 1197 区间素数筛模版

给t给样例，每个样例a,b两个数，求区间[a,b]内素数的个数，(1 ≤ a ≤ b < 2^31, b - a ≤ 100000).

• ### LeetCode Weekly Contest 29解题思路

代码很简单，简单说明下思路就出来了。按照题意，不管怎么二分，整个数组都会被划分成两部分和，这两部分和必然一大一小。如nums = [1,4,3,2]，划分如下[...

• ### LeetCode 45 Jump Game II

这道题目乍一看，我以为是动态规划。可是LeetCode 从来不给数据范围。，又是hard难度的题目，所以我猜测数组长度至少10万吧。