My observation: If we fill a List of intervals with [first appearance, last appearance] for each char. Then the question suddenly turns into the 'merge intervals'
Q: Can worst-case time complexity be reduced in any way ? Yes, the worst-case time complexity can be significantly reduced from O(n^2) to O(n). Here's how we can optimize the algorithm: 1. Use an array to store the last occurrence of each character. 2. Make a single pass through the string to find partitions. Here's an optimized version of the code: ```java class PartitionLabels { public List partitionLabels(String s) { List partitions = new ArrayList(); if (s == null || s.length() == 0) return partitions; // Step 1: Create an array to store the last index of each character int[] lastIndex = new int[26]; for (int i = 0; i < s.length(); i++) { lastIndex[s.charAt(i) - 'a'] = i; } // Step 2: Find partitions in a single pass int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { end = Math.max(end, lastIndex[s.charAt(i) - 'a']); if (i == end) { partitions.add(end - start + 1); start = i + 1; } } return partitions; } } ``` Time Complexity Analysis: 1. The first loop to fill the lastIndex array is O(n). 2. The second loop to find partitions is also O(n). 3. All operations inside the loops are O(1). Therefore, the overall time complexity is O(n), where n is the length of the input string. Space Complexity: 1. We use an additional array of size 26 (constant space). 2. The output list in the worst case could be of size n/2 if every other character forms a partition. The space complexity remains O(n). This optimized version eliminates the nested loops and repeated calls to lastIndexOf, significantly improving the time complexity while maintaining the same space complexity. It's much more efficient, especially for larger inputs.
