LeetCode 763 — Partition Labels

Séptimo problema de Greedy. Particionar string tal que cada letra esté en como mucho una partición. Greedy: precomputar última posición de cada letra.

Enunciado

Particiona s en el máximo número de pedazos tales que ninguna letra aparezca en más de un pedazo.

---

Solución — Greedy con last_occurrence

class Solution:
    def partitionLabels(self, s):
        last = {c: i for i, c in enumerate(s)}    # última posición de cada char
        result = []
        start = end = 0
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                result.append(end - start + 1)
                start = i + 1
        return result

Análisis: O(n).

---

Conexiones

• Próximo: 678-valid-parenthesis-string.

Estado

• Leído
• Implementado desde cero
• Resuelto en LeetCode