【Lintcode】1045. Partition Labels

题目地址：

https://www.lintcode.com/problem/partition-labels/description

给定一个字符串 s s s，要求将其分成若干不相交子串，使得每个字符只出现在其中一个分块之中。要求分块数目尽量大，并且以数组的方式返回分块方案，每个数是分块字符串的长度。题目保证 s s s中只含小写英文字母。

思路是贪心。首先用哈希表存一下每个字符出现的最后位置，然后从左到右遍历 s s s，遍历的同时，用哈希表存的最后出现位置来扩展分块右边界。一开始将分块左端点设置为 0 0 0，如果发现遍历到 s [ i ] s[i] s[i]的时候，右边界恰好就是 i i i，说明 i i i以及其之前的所有字符，也就是 s [ 0 : i ] s[0:i] s[0:i]可以构成一个分块，分好了之后，开始新的分块过程，将分块左端点设为 i + 1 i+1 i+1，然后继续上面的方式遍历，直到遍历完。

算法正确性证明：

首先上述分块一定是合法的，即每个字符最多出现在其中一个分块中。下面证明上面的分块数是最多的。假设最优解的分块位置（这里分块位置定义为每一个分块最后一个字符的下标）和上述做法的位置，第一个不一样的地方是第 k k k个地方，显然最优解的分块位置不能比贪心法的分块位置靠左，否则会出现同一个字母出现在多个分块中的情况，这是不合法的；如果出现在右边，那么可以将最优解在贪心法得到的位置再切一刀，这样就得到了一个分块数更多的更优解，矛盾了。所以贪心法所得的解就是最优解。

代码如下：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    /**
     * @param S: a string
     * @return: a list of integers representing the size of these parts
     */
    public List<Integer> partitionLabels(String S) {
        // Write your code here
        List<Integer> res = new ArrayList<>();
        
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < S.length(); i++) {
            map.put(S.charAt(i), i);
        }
        
        int start = 0, end = 0;
        for (int i = 0; i < S.length(); i++) {
            char ch = S.charAt(i);
            // 更新右边界
            end = Math.max(map.get(ch), end);
            // 如果当前位置恰好是右边界，则做分割，同时将分割出的区间长度加入res
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        
        return res;
    }

}
           

时间复杂度 O ( n ) O(n) O(n)，空间 O ( 1 ) O(1) O(1)（因为英文字母总共 26 26 26个）。