README_EN.md

763. Partition Labels

中文文档

Description

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.

 

Solutions

Python3

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = defaultdict(int)
        n = len(s)
        for i in range(n):
            last[s[i]] = i
        ans = []
        left = right = 0
        for i in range(n):
            right = max(right, last[s[i]])
            if i == right:
                ans.append(right - left + 1)
                left = right + 1
        return ans

Java

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[128];
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            last[s.charAt(i)] = i;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0, left = 0, right = 0; i < n; ++i) {
            right = Math.max(right, last[s.charAt(i)]);
            if (i == right) {
                ans.add(right - left + 1);
                left = right + 1;
            }
        }
        return ans;
    }
}

TypeScript

function partitionLabels(s: string): number[] {
    const n = s.length;
    let last = new Array(128);
    for (let i = 0; i < n; i++) {
        last[s.charCodeAt(i)] = i;
    }
    let ans = [];
    let left = 0,
        right = 0;
    for (let i = 0; i < n; i++) {
        right = Math.max(right, last[s.charCodeAt(i)]);
        if (i == right) {
            ans.push(right - left + 1);
            left = right + 1;
        }
    }
    return ans;
}

C++

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.size();
        vector<int> last(128);
        for (int i = 0; i < n; ++i) last[s[i]] = i;
        vector<int> ans;
        for (int i = 0, left = 0, right = 0; i < n; ++i)
        {
            right = max(right, last[s[i]]);
            if (i == right)
            {
                ans.push_back(right - left + 1);
                left = right + 1;
            }
        }
        return ans;
    }
};

Go

func partitionLabels(s string) []int {
	n := len(s)
	last := make([]int, 128)
	for i := 0; i < n; i++ {
		last[s[i]] = i
	}
	var ans []int
	left, right := 0, 0
	for i := 0; i < n; i++ {
		right = max(right, last[s[i]])
		if i == right {
			ans = append(ans, right-left+1)
			left = right + 1
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...