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 original 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.
Example 1:
Input: s = "ababccc" Output: 5 Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.
Example 2:
Input: s = "aba" Output: 2 Explanation: One way to split maximally is ['a', 'ba'].
Example 3:
Input: s = "aa" Output: 1 Explanation: It is impossible to split the string any further.
Constraints:
1 <= s.length <= 16
s
contains only lower case English letters.
Solution: Brute Force
Try all combinations.
Time complexity: O(2^n)
Space complexity: O(n)
Iterative/C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: int maxUniqueSplit(string_view s) { const int n = s.length(); if (n == 1) return 1; size_t ans = 1; unordered_set<string_view> seen; for (int m = 1; m < 1 << (n - 1); ++m) { if (__builtin_popcount(m) < ans) continue; // 956 ms -> 52 ms bool valid = true; int p = 0; for (int i = 1; i <= n && valid; ++i) { if (m & (1 << (i - 1)) || i == n) { valid &= seen.insert(s.substr(p, i - p)).second; p = i; } } if (valid) ans = max(ans, seen.size()); seen.clear(); } return ans; } }; |
DFS/C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int maxUniqueSplit(string_view s) { size_t ans = 1; const int n = s.length(); unordered_set<string_view> seen; function<void(int)> dfs = [&](int p) { if (p == n) { ans = max(ans, seen.size()); return; } for (int i = p; i < n; ++i) { string_view ss = s.substr(p, i - p + 1); if (!seen.insert(ss).second) continue; dfs(i + 1); seen.erase(ss); } }; dfs(0); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment