求O(n)中有两个唯一字符的子串数

Question

我正在处理一系列子字符串问题：

给出一个字符串：

1. 查找只包含两个最大长度的唯一字符的子字符串。
2. 查找包含最多两个唯一字符的所有子字符串的数目。
3. 查找包含两个唯一字符的所有子字符串的数目。

似乎问题1和问题2有O(n)解。但是，我想不出问题3的O(n)解决方案。(这里是问题2的解决方案，这里是问题1的解决方案。)

所以我想知道问题3的O(n)解是否存在？

为问题3添加示例输入/输出：

Given: abbac

Return: 6

因为有6个子字符串包含两个唯一的字符: ab、abb、abba、bba、ba、ac。

Answer 1

查找包含两个唯一字符的所有子字符串的数目。

编辑：我误解了这个问题。此解决方案找到具有至少两个唯一字符的唯一子字符串。

1. 长度为len的给定单词的子字符串数由len * (len + 1) / 2给出。 sum = len * (len + 1) / 2

1. We are looking for substrings whose length is greater than 1. The above formula includes  substrings which are of length 1. We need to substract those substrings. 

​

所以现在两个字母子串的总数是len * (len + 1) / 2 - l。

sum = `len * (len + 1) / 2 - l`

1. 查找最长的连续运行的字符是相似的。应用步骤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个唯一的字符。这些运行的总和给出了所需子字符串的总数。

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

Answer 2

• 按顺序读取字符串中的字符。用连续字符每次运行的第一个字符的索引、运行的长度以及该字符是否等于所遇到的第二个先前字符来填充数组。调用这个数组A。跟踪正在运行的和并将其初始化为零。打电话给x。

例如，abbaabbccd => (0,1，)，(1,2，)，(3,2，T)，(5,2，T)，(7,2，F)，(9,1，F) =A

• 对于A中的每一个索引I，通过向右移动1找到你得到的索引j，然后继续向右移动，只要你在A的'True‘元素上着陆。

例如，如果是i=0，那么j=3是因为(5,2，T)是真，但是(7,2，F)是假的。

• 设x=x+ (Ai) *(Ak的k= i+1到j的和)

例如，连续的i=0，我们得到1* 6 =6，这对应于所有6‘ab.’以'a‘开头的字符串。

• 现在，运行时间是多少？注意，在步骤2中，通过向右移动到一组真元素，直到找到一个false元素，才能找到j。该元素一直保持不变，直到i= j，此时它再次向右移动。我们有两个指数单调地向右移动，因此处理A在A中是线性的，而在输入中是线性的。

要完成这个示例：(从x=0开始)

• i=0，j=3，x += 6 -> x=6
• i=1，j=3，x += 8 -> x=14
• i=2，j=3，x += 4 -> x=18
• i=3，j=4，x += 4 -> x=22
• i=4，j=5，x += 2 -> x=24

我要指出的是，您不是每次计算从i+1到j的和，而是在每次增加i时将它减少适当的数量，并且只在j增加时重新计算它。

Answer 3

我认为你发布的解决问题的链接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;
}

关于派生的完整解释可以在链接本身中找到:)