Partition Labels Problem


Description

LeetCode Problem 763.

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:

1
2
3
4
5
6
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:

1
2
Input: s = "eccbbbbdec"
Output: [10]

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> res, pos(26, 0);  
        for (auto i = 0; i < S.size(); ++i) 
            pos[S[i] - 'a'] = i;
        for (auto i = 0, idx = INT_MIN, last_i = 0; i < S.size(); ++i) {
            idx = max(idx, pos[S[i] - 'a']);
            if (idx == i) 
                res.push_back(i - exchange(last_i, i + 1) + 1);
        }
        return res;
    }
};




Related Posts

X Of A Kind In A Deck Of Cards Problem

LeetCode 914. In a deck of cards, each card has...

Word Subsets Problem

LeetCode 916. You are given two string arrays words1 and...

Vowel Spellchecker Problem

LeetCode 966. Given a wordlist, we want to implement a...

Verifying An Alien Dictionary Problem

LeetCode 953. In an alien language, surprisingly, they also use...

Unique Morse Code Words Problem

LeetCode 804. International Morse Code defines a standard encoding where...

Unique Email Addresses Problem

LeetCode 929. Every valid email consists of a local name...