aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--partition_labels.c42
-rw-r--r--partition_labels.py34
2 files changed, 76 insertions, 0 deletions
diff --git a/partition_labels.c b/partition_labels.c
new file mode 100644
index 0000000..eb06b60
--- /dev/null
+++ b/partition_labels.c
@@ -0,0 +1,42 @@
+// 763. Partition Labels
+#include "leetcode.h"
+
+/*
+ * you are given a string 's'. we want to partition the string into as many
+ * parts as possible so that each letter appears in at most one part. for
+ * example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note
+ * that the partition is done so that after concatenating all the parts in
+ * order, the resultant string should be 's'. return a list of integers
+ * representing the size of these parts.
+ */
+
+int *partitionLabels(char *s, int *returnSize) {
+ int n = strlen(s), start = 0, end = 0, curr = 0;
+ int *ans = (int *)calloc(n, sizeof(int)), hash[26] = {0};
+ for (int i = 0; i < n; i++)
+ hash[s[i] - 'a'] = i;
+ for (int i = 0; i < n; i++) {
+ int prev = hash[s[i] - 'a'];
+ end = end > prev ? end : prev;
+ if (end == i) {
+ ans[curr++] = end - start + 1;
+ start = end + 1;
+ }
+ }
+ *returnSize = curr;
+ return ans;
+}
+
+int main() {
+ char *s1 = "ababcbacadefegdehijhklij", *s2 = "eccbbbbdec";
+ int rs1, *pl1 = partitionLabels(s1, &rs1);
+ int rs2, *pl2 = partitionLabels(s2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", pl1[i]); // expect: 9 7 8
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", pl2[i]); // expect: 10
+ printf("\n");
+ free(pl1);
+ free(pl2);
+}
diff --git a/partition_labels.py b/partition_labels.py
new file mode 100644
index 0000000..13556c5
--- /dev/null
+++ b/partition_labels.py
@@ -0,0 +1,34 @@
+# 763. Partition Labels
+
+"""
+you are given a string 's'. we want to partition the string into as many
+parts as possible so that each letter appears in at most one part. for
+example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note
+that the partition is done so that after concatenating all the parts in
+order, the resultant string should be 's'. return a list of integers
+representing the size of these parts.
+"""
+
+
+class Solution(object):
+ def partitionLabels(self, s):
+ """
+ :type s: str
+ :rtype: List[int]
+ """
+ curr, ans = 0, [0]
+ ends = {c: i for i, c in enumerate(s)}
+ while curr < len(s):
+ prev = ends[s[curr]]
+ while curr <= prev:
+ sym = s[curr]
+ prev = max(prev, ends[sym])
+ curr += 1
+ ans.append(curr)
+ return [ans[i] - ans[i - 1] for i in range(1, len(ans))]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.partitionLabels(s="ababcbacadefegdehijhklij"))
+ print(obj.partitionLabels(s="eccbbbbdec"))