5

我正在研究一系列子字符串问题：

给定一个字符串：

  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

4

3 回答 3

1

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

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

  1. 给定单词的子字符串数，其长度len由下式给出len * (len + 1) / 2

    总和 =len * (len + 1) / 2

    1. 我们正在寻找长度大于 1 的子字符串。上面的公式包括长度为 1 的子字符串。我们需要减去这些子字符串。

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

sum = `len * (len + 1) / 2 - l`
  1. 找到最长的连续字符，它们是相似的。应用步骤1和2。sum从步骤 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);

}

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
于 2013-07-15T18:06:28.733 回答
0
  • 按顺序读取字符串的字符。用连续字符的每个运行的第一个字符的索引、运行的长度以及字符是否等于遇到的第二个先前字符来填充数组。调用此数组 A。跟踪运行总和并将其初始化为零。称之为 x。

例如，abbaabbccd => [(0,1, ), (1,2, ), (3,2,T), (5,2,T), (7,2,F), (9,1,F )] = 一个

  • 对于 A 中的每个索引 i，通过向右移动 1 找到您到达的索引 j，然后只要您落在 A 的“真”元素上，就继续向右移动。

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

  • 令 x = x + (A[i][1]) * (从 k = i+1 到 j 的 A[k][1] 的总和)

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

  • 现在，运行时间是多少？好吧，请注意在第 2 步中，您通过向右移动穿过一堆真元素直到找到假元素来找到 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 增加时重新计算。

于 2013-07-15T16:20:06.000 回答
0

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

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

于 2015-03-14T10:36:43.990 回答