[LeetCode] 763. Partition Labels

轉自LeetCode

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.

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]

 

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Solution

和 3 .Longest Substring Without Repeating Characters 有點像

也是用到 sliding window 的概念

但不同的是，這在是要在右邊界動手腳

首先先記錄每個 char 最後出現的 index

接著開始歷遍 string，並且記錄目前遇到字元中，最右邊的 index 是多少

如果當下的位置，剛好等於現在最右邊的 index

那就代表找到一個斷點，因為在這個字元之前的所有其他字元，不會再出現了

且本身這個字元也不會再出現了

這時候，也把左邊界更新到目前這個位置，繼續一樣的檢查就可以

kotlin

	class Solution {
	fun partitionLabels(s: String): List<Int> {
	val map = mutableMapOf<Char,Int>()
	for(i in s.indices) {
	map[s[i]] = i // right most position
	}
	val ans = mutableListOf<Int>()
	var start = -1
	var last = 0
	for(i in s.indices) {
	last = Math.max(last, map[s[i]]!!)
	if(i == last) {
	ans.add(last - start)
	start = i
	}
	}
	return ans
	}
	}

view raw partition_labels.kt hosted with ❤ by GitHub