[LeetCode][763. Partition Labels] Greedy Solution with Easy Detailed Explanation

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution Greedy Solution with Easy Detailed Explanation of Problem 763. Partition Labels.

Greedy

If we want to partition, we must maintain Two Pointers at the beginning and the end of a section. The Next Partition will start at the end of last Partition.

While scanning the string, if all the characters in the Partition only appear in the Partition, we can Partition it.

As the picture below shows, the farthest position of all the chars is no more than \(8\), so we can partition it.

and so on.

maxPosition
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static List<Integer> partitionLabels(String s) {
    List<Integer> ans = new ArrayList<>();
    if (s.length() <= 1) {
        ans.add(s.length());
        return ans;
    }

    int len = s.length();
    Map<Character, Integer> idxMap = new HashMap<>();
    for (int i = 0; i < len; i++) {
        char ch = s.charAt(i);
        if (idxMap.containsKey(ch)) {
            idxMap.put(ch, i);
        } else {
            idxMap.put(ch, i);
        }
    }

    int index = 0;
    int[] partSection = new int[2];

    while (index < len) {
        while (index >= partSection[0] && index <= partSection[1]) {
            char ch = s.charAt(index);
            index++;
            int lastIdx = idxMap.get(ch);
            if (lastIdx > partSection[1]) {
                partSection[1] = lastIdx;
            }
        }

        ans.add(partSection[1] - partSection[0] + 1);
        partSection[0] = partSection[1] = index;
    }

    return ans;
}

Analysis

  • Time Complexity: \(O(n)\), we will traversal the string twice.
  • Space Complexity: \(O(|\Sigma|)\)，the \(\Sigma = 26\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗