763. Partition Labels

Array Hash Table Two Pointers String Greedy

Time: O(n)

Space: O(1)

Intuition

Each character can only appear in one partition. Greedy: extend the current partition's end to the last occurrence of each character seen.

Algorithm

1Precompute last occurrence of each character.
2Scan left to right: track current partition end = max of last occurrences of chars seen.
3When i == current end, finalize partition.

Example Walkthrough

Input: "ababcbacadefegdehijhklij"

1.a last=8, b last=5, c last=7 → first partition ends at 8.
2.d last=14, e last=15 → second partition ends at 15.
3.Third partition is rest.

Output: [9,7,8]

Common Pitfalls

•One pass suffices: track end = max(end, last[c]) as you scan.

763.cs

// Approach: Record last occurrence of each character; scan left to right extending the partition boundary, emit a partition when the index reaches the boundary.
// Time: O(n) Space: O(1)

public class Solution
{
    public IList<int> PartitionLabels(string s)
    {
        List<int> ans = new List<int>();
        int[] rightmost = new int[26];

        for (int i = 0; i < s.Length; ++i)
            rightmost[s[i] - 'a'] = i;

        int l = 0; // the leftmost index of the current running string
        int r = 0; // the rightmost index of the current running string

        for (int i = 0; i < s.Length; ++i)
        {
            r = Math.Max(r, rightmost[s[i] - 'a']);
            if (r == i)
            {
                ans.Add(i - l + 1);
                l = i + 1;
            }
        }

        return ans;
    }
}

Was this solution helpful?