algoadvance

Leetcode 763. Partition Labels

Problem Statement:

Given a string s, partition it 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. What is the range of length for string s?
    • The length of s is from 1 to 500.
  2. Does the string contain only lowercase English letters?
    • Yes, the string contains only lowercase English letters.

Strategy:

  1. Last Occurrence Index:
    • First, create an array (or hashmap) to store the last index of each character in the string.
  2. Partitioning:
    • Iterate through the string while maintaining two pointers: start and end.
    • start denotes the beginning of the current partition, and end denotes the farthest point we need to go to include the current character.
    • For each character, update the end pointer to be the maximum of its current value and the last occurrence index of the current character.
    • When the current index reaches the end pointer, it means a partition can be made. Record the size of this partition and update the start pointer to the next character.

Code:

import java.util.*;

public class PartitionLabels {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        
        // Step 1: Record the last occurrence index of each character
        int[] lastOccurrences = new int[26]; // Since there are 26 lowercase English letters
        for (int i = 0; i < s.length(); i++) {
            lastOccurrences[s.charAt(i) - 'a'] = i;
        }
        
        // Step 2: Iterate through the string and partition
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, lastOccurrences[s.charAt(i) - 'a']);
            
            if (i == end) {
                // End of the current partition
                result.add(end - start + 1);
                start = end + 1;
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        PartitionLabels solution = new PartitionLabels();
        String s = "ababcbacadefegdehijhklij";
        List<Integer> result = solution.partitionLabels(s);
        System.out.println(result); // Output should be [9, 7, 8]
    }
}

Time Complexity:

This solution should efficiently solve the problem while ensuring that each character appears in at most one partition, as required.

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