diff options
author | Jack Sangdahl <[email protected]> | 2024-10-20 22:26:30 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-20 22:26:30 -0600 |
commit | 3f53cedfddf11641d652d347b25df64807a4468a (patch) | |
tree | e393b100ce7e88cc9de387cac262caa54b8829c8 | |
parent | 68b8faee8c8cb41cb423bb8a9e34833a290dc22e (diff) | |
download | leetcode-3f53cedfddf11641d652d347b25df64807a4468a.tar.gz leetcode-3f53cedfddf11641d652d347b25df64807a4468a.zip |
1593. split a string into the max number of unique substrings
-rw-r--r-- | split_string_max_unique_substr.c | 70 | ||||
-rw-r--r-- | split_string_max_unique_substr.py | 39 |
2 files changed, 109 insertions, 0 deletions
diff --git a/split_string_max_unique_substr.c b/split_string_max_unique_substr.c new file mode 100644 index 0000000..066cdac --- /dev/null +++ b/split_string_max_unique_substr.c @@ -0,0 +1,70 @@ +// 1593. Split a String Into the Max Number of Unique Substrings +#include "leetcode.h" + +/* + * given a string 's', return the maximum number of unique substrings that the + * given string can be split into. you can split string 's' into any list of + * non-empty substrings, where the concatenation of the substrings forms the + * origin string. however, you must split the substrings such that all of them + * are unique. a substring is a contiguous sequence of characters within a + * string. + */ + +struct map { + int len; + char s[16]; +}; + +bool find(struct map *m, int idx, char *tmp, int tmp_len) { + if (idx == -1) + return false; + for (int i = 0; i <= idx; i++) + if (m[i].len == tmp_len) + if (!strncmp(m[i].s, tmp, tmp_len)) + return true; + return false; +} + +bool is_valid(char *s, int s_len, int split, int *active_bits) { + struct map m[s_len]; + int idx = -1, tmp_len = 1; + char tmp[s_len]; + memcpy(&tmp[0], &s[0], 1); + for (int i = 0; i < s_len - 1; i++) { + if ((split >> i) & 1) { + if (find(m, idx, tmp, tmp_len)) + return false; + idx++; + memcpy(&(m[idx].s), &tmp[0], tmp_len); + m[idx].s[tmp_len] = '\0'; + m[idx].len = tmp_len; + (*active_bits)++; + tmp_len = 0; + tmp[tmp_len++] = s[i + 1]; + } else + tmp[tmp_len++] = s[i + 1]; + } + if (tmp_len && find(m, idx, tmp, tmp_len)) + return false; + return true; +} + +int maxUniqueSplit(char *s) { + int n = strlen(s); + if (n == 1) + return 1; + int max_size = pow(2, n - 1), max_split = 0; + for (int i = 0; i < max_size; i++) { + int m = 0; + if (is_valid(s, n, i, &m)) + max_split = fmax(max_split, m); + } + return max_split + 1; +} + +int main() { + char *s1 = "ababccc", *s2 = "aba", *s3 = "aa"; + printf("%d\n", maxUniqueSplit(s1)); // expect: 5 + printf("%d\n", maxUniqueSplit(s2)); // expect: 2 + printf("%d\n", maxUniqueSplit(s3)); // expect: 1 +} diff --git a/split_string_max_unique_substr.py b/split_string_max_unique_substr.py new file mode 100644 index 0000000..354e9c8 --- /dev/null +++ b/split_string_max_unique_substr.py @@ -0,0 +1,39 @@ +# 1593. Split a String Into the Max Number of Unique Substrings + +""" +given a string 's', return the maximum number of unique substrings that the +given string can be split into. you can split string 's' into any list of +non-empty substrings, where the concatenation of the substrings forms the +origin string. however, you must split the substrings such that all of them +are unique. a substring is a contiguous sequence of characters within a +string. +""" + + +class Solution(object): + def maxUniqueSplit(self, s): + """ + :type s: str + :rtype: int + """ + + def backtrack(beg, vis): + if beg == len(s): + return 0 + max_split = 0 + for end in range(beg + 1, len(s) + 1): + substr = s[beg:end] + if substr not in vis: + vis.add(substr) + max_split = max(max_split, backtrack(end, vis) + 1) + vis.remove(substr) + return max_split + + return backtrack(0, set()) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxUniqueSplit(s="ababccc")) + print(obj.maxUniqueSplit(s="aba")) + print(obj.maxUniqueSplit(s="aa")) |