Partition Labels LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Microsoft Nutanix Oracle Uber VMware YandexViews 3813

Problem Statement

Partition Labels LeetCode Solution – 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.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Examples and Explanation

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.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]
Explanation: 
The given string can not partitioned further as the letters will be repeated if partitioned.

Algorithm

Let’s look at example 1, we can notice that if we are including ‘a’ in the first partition then we need to include all the ‘a’s appearing in the string. So, we will include the substring from the first index till the last index of occurrences of ‘a’. In the second partition, "defegde" , we notice that including substring from the first index of ‘d’ till the last index of ‘d’ will not suffice. This means that we need to include all the last indices of all letters appearing between the first and last indices of ‘d’ as well.

Partition Labels LeetCode Solution

Code

C++ program for Partition Labels

class Solution {
public:
    vector<int> partitionLabels(string s) {
        map<char,int> index;
        for(int i=0; i<s.size(); i++) {
            index[s[i]]=i;
        }
        vector<int>res;
        int pivot=0;
        int last_index=0;
        for(int curr=0; curr<s.size(); curr++) {
            last_index = max(last_index, index[s[curr]]);
            if(curr == last_index) {
                res.push_back(last_index-pivot+1);
                pivot=curr+1;
            }
        }
        return res;
    }
};

Java program for Partition Labels

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] index = new int[26];
        for (int i = 0; i < s.length(); ++i)
            index[s.charAt(i) - 'a'] = i;
        
        List<Integer> res= new ArrayList();
        int pivot=0;
        int last_index=0;
        for(int curr=0; curr <s.length(); curr++) {
            last_index = Math.max(last_index, index[s.charAt(curr) - 'a']);
            if(curr == last_index) {
                res.add(last_index-pivot+1);
                pivot=curr+1;
            }
        }
        return res;
    }
}

Complexity Analysis for Partition Labels LeetCode Solution

  • Time Complexity: O(N), where N is the length of the given string
  • Space Complexity: O(1)
    • Although we have defined a map, its size will be limited to 26, hence constant size
Translate »