763. Partition Labels

A string S of lowercase English 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 English letters ('a' to 'z') only.

分析1：

遍历S一遍，记录每个element出现的频率。

再遍历S时，只要当前substring的所有element都满足了出现频率后，就可以开始下一轮substring。

一开始在想check频率的时候loop through dictionary，后来发现其实不用，拿一个stack来store unfulfiled element，每次遍历check stack是不是空的就行

Solution：

class Solution(object):
 def partitionLabels(self, S):
 “””
 :type S: str
 :rtype: List[int]
 “””
 myMap = {}
 ans = []
 newMap = {}
 count = 0
 stack = []
 
 for each in S:
   if each in myMap:
     myMap[each] += 1
   else:
     myMap[each] = 1
 
 for each in S:
   count+= 1
   if each not in newMap:
     newMap[each] = 1
     stack.append(each)
   else:
     newMap[each] += 1
   if newMap[each] == myMap[each]:
   stack.remove(each)
   if not stack:
     ans.append(count)
     count = 0
     newMap = {}
 
 return ans

分析2：

看到了一个更简洁的方法，直接用2pointer就能解决。

遍历S后找到每个element最后出现的位置，

再遍历substring的时候，每次loop就update右边的pointer，直到两个pointer重合，然后开始下一个substring。

牛皮

Figure out the rightmost index first and use it to denote the start of the next section.

Reset the left pointer at the start of each new section.

Store the difference of right and left pointers + 1 as in the result for each section.

def partition_labels(S):
	rightmost = {c:i for i, c in enumerate(S)}
	left, right = 0, 0
	result = []
	for i, letter in enumerate(S):
		right = max(right,rightmost[letter])
	
		if i == right:
			result += [right-left + 1]
			left = i+1
	return result