###### tags: `Leetcode` `medium` `pointer` `hash` `string` `greedy` `python` `c++` `Top 100 Liked Questions`

# 763. Partition Labels

## [題目連結:] https://leetcode.com/problems/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]

## 解題想法:
* 此題為給一字串S，求對其分割為多個子字符串
* 條件為: 每種字符只能出現於一個子字串中

* 想法: 如何找到自符串的斷點(拆分位置)??
* 初始需要工具:
* dic={}: 用以紀錄每個字符**最後**出現的位置
* 先遍歷S紀錄
* cur_cut=0: 紀錄當前字串切斷的位置
* pre_pos=0: 紀錄當前字串起始位置
* 第二次從頭遍歷S:
* 每次更新cur_cut=max(cur_cut, dic[cur_cut])
* 更新為最遠要切到的位置
* 若目前位置==cur_cut:
* **代表可以切斷**
* 解釋: 因為每次遍歷當前的自符，都會更新cur_cut為該字符最遠出現的位置，所以**當目前遇到的字符已經到該最後出現位置了**，表示在pre_pos與cur_cut位置之間的自符，一定都符合只出現於此區間的字串中
* 所以:
* 紀錄該長度
* 將pre_pos=cur_cut+1: 更新下一個字串起始位置

## Python:

class Solution(object):
    def partitionLabels(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        #紀錄每個字母最後出現的位置
        dic={}
        for pos,char in enumerate(s):
            dic[char]=pos
        cur_cut=0 #紀錄當前字串切斷的位置
        pre_pos=0 #紀錄當前字串起始位置
        res=[]
        for pos,char in enumerate(s):
            cur_cut=max(cur_cut,dic[char]) #更新最遠要切的位置
            #若目前遇到的字已經到該最後出現位置了
            #代表可以切斷
            if pos==cur_cut:
                res.append(cur_cut-pre_pos+1)
                pre_pos=cur_cut+1   #更新下個起始位置
        return res

result=Solution()
ans=result.partitionLabels(s = "ababcbacadefegdehijhklij")
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> dic;
        for (int i=0; i<s.size(); i++) dic[s[i]]=i;
        vector<int> res;
        int cur_cut=0, pre_pos=0;
        for (int i=0; i<s.size(); i++){
            //upload the cutPos
            cur_cut=max(cur_cut, dic[s[i]]);
            //can cut
            if (i==cur_cut){
                res.push_back(cur_cut-pre_pos+1);
                pre_pos=i+1;
            }
        }
        return res;
    }
};