# 2405. Optimal Partition of String
https://leetcode.com/problems/optimal-partition-of-string/description/
###### tags: `Python`,`Leetcode`,`Greedy`

## MyCode

class Solution:
    def partitionString(self, s: str) -> int:
        count = 1 
        mark_of_substring_head = 0 
        chr_seen_record =[-1]* 26 
        for i in range(len(s)): 
            if chr_seen_record[ord(s[i]) - ord('a')] >= mark_of_substring_head :
                count += 1
                mark_of_substring_head = i
            chr_seen_record[ord(s[i]) - ord('a')] = i 
        return count

## 題意
* 題目會給一個 string `s` ，我們要做的事就是算這個 string **最少**可以被切成幾個 substring
1. 每個 substring 中的 chr 不能重複

* example 1

Input: s = "abacaba"
Output: 4
Explanation:
Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").
It can be shown that 4 is the minimum number of substrings needed.

* example 2

Input: s = "ssssss"
Output: 6
Explanation:
The only valid partition is ("s","s","s","s","s","s").

## 直覺 ＆ 思路
### 直覺
* **Greedy**：從 `s` 的開頭開始看何時 string 要切，盡量長到不能再長再切（就是遇到相同 chr 再切）
### 思路
* 依照題目 constraint :

1 <= s.length <= 105
s consists of only English lowercase letters.

1. 創造一個 array 出來，大小 26。用來追蹤目前 substring 的 chr
2. 小補充：其實可以使用 Hashset ，但會有額外操作（而且我不太會），所以這邊沒用

## 解法
* 使用：
1. 兩個變數

        count = 1 # 用來記分了幾段用
        mark_of_substring_head = 0 
        # 用來記 substring 的開頭字母 index ，下次遇到這個字母，要多分一段（coun t+ 1）時，要更新下一個 substring 開頭的 index（更新成新遇到的字母 index ）

* eg. example 1 :
1. s = abacaba。 mark_of_substring_head = 0 （s = `a`）
2. 當 index = 2 時遇到第二個 `a`
3. 這個 `a` 要被切到下一段
4. 故下一段 substring 開頭字母的 index 會更新至 2
5. 下一段會成為一個新的 substring ，故 count += 1
2. 一個 array

        chr_seen_record =[-1]* 26 
    # 26 個字母，只要經過 s[i]，就會在相對應的位置上留下記號（這個記號就是原本的 substring s[i] 的 i）

3. 一個 for 迴圈

        # 使用 ord() 函數返回 ASCII 值，得知目前的字母並作記號，下一次遇到同字母，就要跳到下一段分裂
        for i in range(len(s)): 
            if chr_seen_record[ord(s[i]) - ord('a')] >= mark_of_substring_head :
                count += 1
                mark_of_substring_head = i
                # chr_seen_record[ord(s[i]) - ord('a')] == mark_of_substring_head 出現在第一次切
                # chr_seen_record[ord(s[i]) - ord('a')] > mark_of_substring_head 出現在第二次切 
            chr_seen_record[ord(s[i]) - ord('a')] = i 
        return count