[LeetCode] 763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

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.

Example 2:
Input: s = “eccbbbbdec”
Output: [10]

Constraints:
1 <= s.length <= 500
s consists of lowercase English letters.

划分字母区间。

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是贪心 + 双指针。首先遍历一次字符串，将每个字符最后一次出现的 index 记录下来。再遍历一次字符串，这一次需要用到两个指针，start 指针一开始在字符串的起始部位，end 指针一点点随着 i 指针往后走，每次看到一个字母，end 就更新为当前遍历到的所有字母中间的最后一个出现的位置。如果在某一个 i 发现这是当前字母最后一次出现的位置，则说明当前 i 位置上这个字母之后再也不可能遇到，可以开始分割 input 了，(start, i)，然后下一个分段则是从 i + 1 开始。

这里我引用一个截图以帮助理解。我们用 end 指针扫描字符串的时候，比如一开始的 a，我们根据 last 数组可知最后一次出现 a 的下标是 8，我们就可以将 end 指针更新到 8 的位置。如果在下标 1 - 8 之间有其他字母的最后一次出现位置的下标 > 8 的话，我们还需要再更新 end 指针的位置，这样才能确保 start - end 之间所有的字母在同一个被分割的片段里。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] map = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map[c - 'a'] = i;
        }

        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            end = Math.max(end, map[c - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}