##### Welcome to Subscribe On Youtube
• import java.util.ArrayList;
import java.util.List;

/**

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:
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 letters ('a' to 'z') only.

*/

public class Partition_Labels {

class Solution {
public List<Integer> partitionLabels(String s) {

List<Integer> result = new ArrayList<>();

if (s == null || s.length() == 0) {
return result;
}

int[] lastSeenAt = new int[256];
for (int i = 0; i < s.length(); i++) {
lastSeenAt[s.charAt(i) - 'a'] = i;
}

int j = 0;
int anchor = 0;
for (int i = 0; i < s.length(); i++) {
j = Math.max(j, lastSeenAt[s.charAt(i) - 'a']);

if (i == j) {
result.add(j - anchor + 1);
anchor = j + 1;
}
}

return result;
}
}
}

############

class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
int n = s.length();
for (int i = 0; i < n; ++i) {
last[s.charAt(i) - 'a'] = 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) - 'a']);
if (i == right) {
ans.add(right - left + 1);
left = right + 1;
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/partition-labels/
// Time: O(S)
// Space: O(1)
class Solution {
public:
vector<int> partitionLabels(string s) {
int N = s.size(), last[26] = {};
memset(last, -1, sizeof(last));
for (int i = 0; i < N; ++i) last[s[i] - 'a'] = i;
vector<int> ans;
for (int i = 0; i < N;) {
int start = i;
for (int end = i + 1; i < end; ++i) end = max(end, last[s[i] - 'a'] + 1);
ans.push_back(i - start);
}
return ans;
}
};

• class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)}
ans = []
left = right = 0
for i, c in enumerate(s):
right = max(right, last[c])
if i == right:
ans.append(right - left + 1)
left = right + 1
return ans

############

class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
lindex = {c: i for i, c in enumerate(S)}
j = anchor = 0
ans = []
for i, c in enumerate(S):
j = max(j, lindex[c])
if i == j:
ans.append(j - anchor + 1)
anchor = j + 1
return ans

• func partitionLabels(s string) []int {
last := make([]int, 26)
n := len(s)
for i := 0; i < n; i++ {
last[s[i]-'a'] = i
}
var ans []int
for i, left, right := 0, 0, 0; i < n; i++ {
right = max(right, last[s[i]-'a'])
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
}

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


• /**
* @param {string} s
* @return {number[]}
*/
var partitionLabels = function (s) {
const n = s.length;
let last = new Array(26);
for (let i = 0; i < n; i++) {
last[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
}
let ans = [];
let left = 0,
right = 0;
for (let i = 0; i < n; i++) {
right = Math.max(right, last[s.charCodeAt(i) - 'a'.charCodeAt(0)]);
if (i == right) {
ans.push(right - left + 1);
left = right + 1;
}
}
return ans;
};


• impl Solution {
pub fn partition_labels(s: String) -> Vec<i32> {
let n = s.len();
let bytes = s.as_bytes();
let mut inx_arr = [0; 26];
for i in 0..n {
inx_arr[(bytes[i] - b'a') as usize] = i;
}
let mut res = vec![];
let mut left = 0;
let mut right = 0;
for i in 0..n {
right = right.max(inx_arr[(bytes[i] - b'a') as usize]);
if right == i {
res.push((right - left + 1) as i32);
left = i + 1;
}
}
res
}
}


• class Solution {
public List<Integer> partitionLabels(String S) {
int[] endArray = new int[26];
Arrays.fill(endArray, -1);
int length = S.length();
for (int i = 0; i < length; i++) {
char c = S.charAt(i);
int letterIndex = c - 'a';
endArray[letterIndex] = i;
}
List<Integer> partition = new ArrayList<Integer>();
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
char c = S.charAt(i);
int letterIndex = c - 'a';
int curEnd = endArray[letterIndex];
end = Math.max(end, curEnd);
if (i == end) {
partition.add(end - start + 1);
start = i + 1;
}
}
return partition;
}
}

############

class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
int n = s.length();
for (int i = 0; i < n; ++i) {
last[s.charAt(i) - 'a'] = 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) - 'a']);
if (i == right) {
ans.add(right - left + 1);
left = right + 1;
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/partition-labels/
// Time: O(S)
// Space: O(1)
class Solution {
public:
vector<int> partitionLabels(string s) {
int N = s.size(), last[26] = {};
memset(last, -1, sizeof(last));
for (int i = 0; i < N; ++i) last[s[i] - 'a'] = i;
vector<int> ans;
for (int i = 0; i < N;) {
int start = i;
for (int end = i + 1; i < end; ++i) end = max(end, last[s[i] - 'a'] + 1);
ans.push_back(i - start);
}
return ans;
}
};

• class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)}
ans = []
left = right = 0
for i, c in enumerate(s):
right = max(right, last[c])
if i == right:
ans.append(right - left + 1)
left = right + 1
return ans

############

class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
lindex = {c: i for i, c in enumerate(S)}
j = anchor = 0
ans = []
for i, c in enumerate(S):
j = max(j, lindex[c])
if i == j:
ans.append(j - anchor + 1)
anchor = j + 1
return ans

• func partitionLabels(s string) []int {
last := make([]int, 26)
n := len(s)
for i := 0; i < n; i++ {
last[s[i]-'a'] = i
}
var ans []int
for i, left, right := 0, 0, 0; i < n; i++ {
right = max(right, last[s[i]-'a'])
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
}

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


• /**
* @param {string} s
* @return {number[]}
*/
var partitionLabels = function (s) {
const n = s.length;
let last = new Array(26);
for (let i = 0; i < n; i++) {
last[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
}
let ans = [];
let left = 0,
right = 0;
for (let i = 0; i < n; i++) {
right = Math.max(right, last[s.charCodeAt(i) - 'a'.charCodeAt(0)]);
if (i == right) {
ans.push(right - left + 1);
left = right + 1;
}
}
return ans;
};


• impl Solution {
pub fn partition_labels(s: String) -> Vec<i32> {
let n = s.len();
let bytes = s.as_bytes();
let mut inx_arr = [0; 26];
for i in 0..n {
inx_arr[(bytes[i] - b'a') as usize] = i;
}
let mut res = vec![];
let mut left = 0;
let mut right = 0;
for i in 0..n {
right = right.max(inx_arr[(bytes[i] - b'a') as usize]);
if right == i {
res.push((right - left + 1) as i32);
left = i + 1;
}
}
res
}
}