aboutsummaryrefslogtreecommitdiff
path: root/partition_labels.c
diff options
context:
space:
mode:
Diffstat (limited to 'partition_labels.c')
-rw-r--r--partition_labels.c42
1 files changed, 42 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);
+}