PartitionLabels [source code]

public class PartitionLabels {
static
/******************************************************************************/
class Solution {
    public List<Integer> partitionLabels(String S) {
        Integer[][] positions = new Integer[26][2];
        char[] chs = S.toCharArray ();
        for (int i = 0; i < chs.length; i++) {
            int index = chs[i] - 'a';
            if (positions[index][0] == null)
                positions[index][0] = i;
            positions[index][1] = i;
        }
        List<Integer> resLs = new ArrayList<> ();
        int pos = 0, end = 0, anchor = 0;
        while (pos < chs.length) {
            end = Math.max (positions[chs[pos] - 'a'][1], end);
            if (pos == end) {
                resLs.add (pos - anchor + 1);
                anchor = pos + 1;
            }
            pos++;
        }
        return resLs;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        PartitionLabels.Solution tester = new PartitionLabels.Solution();
    }
}

总体来说不算难的题目, 秒杀, 速度是16ms (NA). 注意这里我对于每一个char记录了leftmost和rightmost两个occurrence, 但是这题其实只需要一个;

另外这题我记录occurrence的时候用integer是因为Integer的special value是自动的, 如果用int, 那么我还要专门在一开始的时候走一遍全都填上-1的special value, 怕麻烦了;

discussion最优解跟我的算法基本是一样的, 不过这里有另外一个解法, 居然真的用sliding window来做这个题目了:

@ashish53v said in Easy O(n) Java solution using sliding window (two pointers), comments and explanation given:

The idea is to use sliding window to add all the chars which are not exhausted yet
use a hashset to know if current char is new or we have seen it before in the current window
if we find new char, increase counter
if we exhausted all char c (table[c-'a'] == 0) in the current window, then decrease counter
if counter becomes 0, it means that current window is a partition, add it to the result list and reset window

Note that counter is incremented when we see a new char in the current window which has not been seen before and it is decremented when count of current char in table becomes zero,
so at any point, the counter indicates the number of chars in the current window which has not been exhausted.
Hope this helps.

class Solution {  
    public List<Integer> partitionLabels(String S) {  
        List<Integer> res = new ArrayList<>();  

        int[] table = new int[26];  
        char[] stc = S.toCharArray();  
        for(char c:stc)//count the occurence of each char in string  
            table[c-'a']++;  

        int i = 0, j = 0, l = S.length(), counter = 0;  
        HashSet<Character> hs = new HashSet<>();  
        while(j < l){  
            char c = stc[j];  
            if(!hs.contains(c)){// found new char in current window, so increase counter  
                hs.add(c);  
                counter++;  
            }  
            table[c-'a']--;  
            j++;  
            if(table[c-'a'] == 0){ // decrease the counter as we have exhausted the c char and remove char c from set  
                counter--;  
                hs.remove(c);  
            }  
            if(counter == 0){//if counter becomes 0, means current window is a partition  
                res.add(j - i);//add length of current window  
                i = j;// reset i for next window  
            }              
        }   
        return res;  
    }  
}

submission暂时看不到;

Problem Description

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:

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

Difficulty:Medium
Total Accepted:1.6K
Total Submissions:2.4K
Contributor:awice
Companies
amazon
Related Topics
greedy

Hint 1
Try to greedily choose the smallest partition that includes the first letter. If you have something like "abaccbdeffed", then you might need to add b. You can use an map like "last['b'] = 5" to help you expand the width of your partition.