Interview 150
Partition Labels
- Problem
- LC 763
- File
- interview150_LC763PartitionLabels.java
- Path
- pkg5leetcode/interview150/interview150_LC763PartitionLabels.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC763PartitionLabels.java
- Approach
- Track last index of each char; extend partition end.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Partition Labels | LC 7635 * APPROACH: Track last index of each char; extend partition end.6 * COMPLEXITY: Time O(n), Space O(1)7 */8import java.util.*;9 10public class interview150_LC763PartitionLabels {11 static List<Integer> partitionLabels(String s) {12 int[] last = new int[26];13 for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;14 List<Integer> res = new ArrayList<>();15 int start = 0, end = 0;16 for (int i = 0; i < s.length(); i++) {17 end = Math.max(end, last[s.charAt(i) - 'a']);18 if (i == end) {19 res.add(end - start + 1);20 start = i + 1;21 }22 }23 return res;24 }25 26 public static void main(String[] args) {27 check(partitionLabels("ababcbacaldefegdehijhklij").equals(Arrays.asList(9, 7, 8)), "case1");28 check(partitionLabels("eccbbbbdec").equals(Arrays.asList(10)), "case2");29 System.out.println("all tests passed");30 }31 32 static void check(boolean cond, String name) {33 if (!cond) throw new AssertionError("FAILED: " + name);34 System.out.println(" PASS " + name);35 }36}