sum = `len * (len + 1) / 2 - l`
1
和2
。从步骤2获得的sum
减去当前总和。以下是示例实现。
public static int allUniq2Substrings(char s[]) {
int sum = s.length * (s.length + 1) / 2 - s.length;
int sameRun = 0;
for (int i = 0, prev = -1; i < s.length; prev = s[i++]) {
if (s[i] != prev) {
sum -= sameRun * (sameRun + 1) / 2 - sameRun;
sameRun = 1;
} else {
sameRun++;
}
}
return sum - (sameRun * (sameRun + 1) / 2 - sameRun);
}
allUniq2Substrings("aaac".toCharArray());
3
allUniq2Substrings("aabc".toCharArray());
5
allUniq2Substrings("aaa".toCharArray());
0
allUniq2Substrings("abcd".toCharArray());
6
编辑 让我再试一次。我使用上面的3个不变量。 这是找到包含至少2个唯一字符的所有子字符串的子问题。 我已经发布了一种方法,可以为任何长度提供唯一的子字符串。我将使用它从包含2个唯一字符的集合生成子字符串。
我们只需要跟踪具有集合长度为2的最长连续字符运行即可。即任意2个唯一字符的排列。这些运行的总和给出了我们所需子字符串的总数。
public static int allUniq2Substrings(char s[]) {
int sum = s.length * (s.length + 1) / 2 - s.length;
int sameRun = 0;
for (int i = 0, prev = -1; i < s.length; prev = s[i++]) {
if (s[i] != prev) {
sum -= sameRun * (sameRun + 1) / 2 - sameRun;
sameRun = 1;
} else {
sameRun++;
}
}
return sum - (sameRun * (sameRun + 1) / 2 - sameRun);
}
public static int uniq2substring(char s[]) {
int last = 0, secondLast = 0;
int sum = 0;
for (int i = 1; i < s.length; i++) {
if (s[i] != s[i - 1]) {
last = i;
break;
}
}
boolean OneTwo = false;
int oneTwoIdx = -1; //alternating pattern
for (int i = last + 1; i < s.length; ++i) {
if (s[secondLast] != s[i] && s[last] != s[i]) { //detected more than 2 uniq chars
sum += allUniq2Substrings(Arrays.copyOfRange(s, secondLast, i));
secondLast = last;
last = i;
if (OneTwo) {
secondLast = oneTwoIdx;
}
OneTwo = false;
} else if (s[i] != last) { //alternating pattern detected a*b*a
OneTwo = true;
oneTwoIdx = i;
}
}
return sum + allUniq2Substrings(Arrays.copyOfRange(s, secondLast, s.length));
}
uniq2substring("abaac".toCharArray())
6
uniq2substring("aab".toCharArray())
2
uniq2substring("aabb".toCharArray())
4
uniq2substring("ab".toCharArray())
1
我认为你发布的链接是解决问题2的方案。
http://coders-stop.blogspot.in/2012/09/directi-online-test-number-of.html
我们可以很容易地将其建模为解决第三个问题的解决方案。 只需按以下方式修改驱动程序即可
int numberOfSubstrings ( string A ) {
int len = A.length();
int res = 0, j = 1, c = 1, a[2][2];
a[0][0] = A[0]; a[0][1] = 1;
for(int i=0;i<len;i++) {
>>int start = -1;
for (;j<len; j++) {
c = isInArray(a, c, A[j]);
>> if (c == 2 && start != - 1) start = j;
if(c == -1) break;
}
>>c = removeFromArray(a,A[i]);
res = (res + j - start);
}
return res;
}