What is the best way to solve Partition Labels?

The optimized O(n) approach using Greedy patterns is generally preferred.

상위 150개 인터뷰쉬움

파티션 레이블

'파티션 레이블' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

문자열 s가 주어집니다. 우리는 각 문자가 많아야 한 부분에 나타나도록 문자열을 가능한 한 많은 부분으로 분할하려고 합니다. 이러한 부분의 크기를 나타내는 정수 목록을 반환합니다.

partitionLabels(s: str) -> List[int] 함수를 작성하세요.

제약

•1 <= len(s) <= 500
•s consists of lowercase English letters

예

Example 1

Input

s = "ababcbacadefegdehijhklij"

Output

[9,7,8]

Explanation

The partition is "ababcbaca", "defegde", "hijhklij".

Example 2

Input

s = "eccbbbbdec"

Output

[10]

Explanation

All characters in 'eccbbbbdec' can only be in one group.

Need a Hint?

세트나 힙과 같은 Greedy 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

Greedy 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def partition_labels_opt(s):
    lastIndex = {c: i for i, c in enumerate(s)}
    res = []; size, end = 0, 0
    for i, c in enumerate(s):
        size += 1; end = max(end, lastIndex[c])
        if i == end: res.append(size); size = 0
    return res

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def partition_labels_brute(s):
    res = []
    i = 0
    while i < len(s):
        last = s.rindex(s[i])
        j = i + 1
        while j < last:
            last = max(last, s.rindex(s[j]))
            j += 1
        res.append(last - i + 1)
        i = last + 1
    return res