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
    }
}

763 - Partition Labels

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions