给出一个由小写字母组成的字符串S。我们希望将这个字符串分成尽可能多的部分，以便每个字母最多出现在一个部分中，并返回表示每个部分大小的整数列表。
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
说明: 分区是“ababcbaca”、“defegde”、“hijhklij”。 这是一个分区，以便每个字母最多出现在一个部分中。
像“ababcbacadefegde”、“hijhklij”这样的分区是不正确的，因为它将 S 分成更少的部分。
下面是我针对上述问题的代码:
class Solution {
public List<Integer> partitionLabels(String S) {
char[] st = S.toCharArray();
int k=0,c=0;
List<Integer> res = new ArrayList<Integer> ();
Set<Integer> visited = new HashSet<Integer> ();
for(int i=0 ; i<st.length ; i++)
{
int idx = S.lastIndexOf(st[i]);
if(visited.add(i) && idx>i && idx>k)
{
k = Math.max(k,idx);
visited.add(k);
}
else if(i == k)
{
res.add(i-c+1);
c=i+1;
k++;
}
}
return res;
}
}
上面的代码可以工作，而且上面代码的时间复杂度为 O(n)，因为它访问每个元素一次。
但是空间复杂度是多少呢？由于我使用的 Char 数组的大小与 String S 的大小相同，并且使用的 Set 的最大大小可以是 String S 的大小，所以它也是 O(n) 吗？
最佳答案
由于您仅使用一维数组并列出您的空间复杂度为 O(n)。
但是你的时间复杂度是 O(n²)，因为 S.lastIndexOf(st[i]); 是 O(n)。
如果您还希望时间为 O(n)，则必须预处理字符串一次 (= O(n)) 以确定每个字符的最后一次出现，例如使用 map 来保持检索时间 O(1)。
关于java - 分区标签问题的空间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55738885/