algoadvance

Leetcode 763. Partition Labels

Problem Statement:

You are given a string s. 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.

Clarifying Questions:

1. Input Format:
   • Is the input string s guaranteed to be non-empty and consist only of lowercase English letters?
   • What is the maximum length of the input string?
2. Output Format:
   • Should the output be a list of integers representing the size of the partitions?

Let’s assume:

• The input string s is non-empty and contains only lowercase English letters.
• The maximum length of the string is reasonably large, up to 500 or so.

Strategy:

To solve this problem, we can use the following approach:

1. First, create a map to record the last occurrence of each character in the string.
2. Initialize pointers to keep track of the start and end of the current partition.
3. Iterate through the string. For each character, update the end of the current partition to the maximum of the current end and the last occurrence of the character.
4. If the current index matches the end of the current partition, it means we have found a valid partition. Record the size of this partition and update the start of the next partition to be the next index.

Code:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

vector<int> partitionLabels(string s) {
    // Step 1: Record the last occurrence of each character.
    unordered_map<char, int> last_occurrence;
    for (int i = 0; i < s.size(); ++i) {
        last_occurrence[s[i]] = i;
    }

    // Step 2: Initialize variables to track partitions.
    int start = 0, end = 0;
    vector<int> partitions;

    // Step 3: Iterate through the string to find partitions.
    for (int i = 0; i < s.size(); ++i) {
        end = max(end, last_occurrence[s[i]]);
        if (i == end) {
            partitions.push_back(end - start + 1);
            start = i + 1;
        }
    }

    return partitions;
}

// Example usage:
int main() {
    string s = "ababcbacadefegdehijhklij";
    vector<int> partitionSizes = partitionLabels(s);
    
    for (int size : partitionSizes) {
        cout << size << " ";
    }
    cout << endl;

    return 0;
}

Explanation:

1. Step 1: We determine the last occurrence of each character in the string using an unordered map.
2. Step 2: We use two variables, start and end, to keep track of the current partition boundaries.
3. Step 3: We iterate through the string, updating the boundary end whenever we encounter a character whose last occurrence is further to the right. When the current index i matches the end, it means we have completed a partition and we can record its size.

Time Complexity:

• Time Complexity: O(n), where n is the length of string s. We traverse the string twice—once to record the last occurrences and once to construct the partitions.
• Space Complexity: O(1). Although we use a map to store the last occurrence of characters, the space complexity remains O(1) since the map stores at most 26 entries (one for each letter in the English alphabet).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?