0%

Leetcode763-partitionLabels

Description

A string S of lowercase 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
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.

Note:

  1. S will have length in range [1, 500].
  2. S will consist of lowercase letters (‘a’ to ‘z’) only.
  3. Solution

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public List<Integer> partitionLabels(String S) {
    List<Integer> res = new ArrayList<>();
    if (S == null || S.length() == 0) return res;

    int[] index = new int[26];
    for (int i = 0; i < S.length(); i++){
    index[S.charAt(i) - 'a'] = i;
    }

    int start = 0;
    int end = 0;
    for (int i = 0; i < S.length(); i++){
    end = Math.max(end, index[S.charAt(i) - 'a']);
    if (end == i){
    res.add(end - start + 1);
    start = end + 1;
    }
    }

    return res;
    }
    }