LeetCode #763: Partition Labels, Greedy Cuts From Last Occurrence

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: split the string into as many parts as possible so that each letter shows up in only one part. Return the size of each part. Brute force: try every set of cut points and check each one, which is very slow. The key insight: a part can't end until it reaches the last position of every letter inside it. Record the last index of each letter. While scanning, extend the end of the current part to the furthest last index seen so far. When i reaches that end, make a cut and start a new part. Dry run: ababcbacadefegdehijhklij splits into parts of size 9, 7 and 8. Complexity: O(N) time and O(1) space, since there are only 26 letters. Problem: https://leetcode.com/problems/partiti... Related: Merge Intervals (56), Jump Game II (45), Optimal Partition of String (2405) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode763 #partitionlabels #greedy #twopointers #hashtable #string #medium #coding #codinginterview #dsa #python #amazon #faang #brutetobest