在O(n)时间内解决具有两个唯一字符的子字符串数量问题

Question

我正在解决一系列子字符串问题：

给定一个字符串：

1. 找到包含仅两个唯一字符的子字符串，其长度最大。

2. 找到包含最多两个唯一字符的所有子字符串的数量。

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

看起来问题1和2有O(n)的解决方案。然而，我无法想出问题3的O(n)解决方案。（这里是问题2的解决方案，这里是问题1的解决方案。）

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

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

给定：abbac

返回：6

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

- Jun

---

当给定一个最多有两个不同字符的字符串时，你能否找出它包含多少非空子串？其中有多少只有一个唯一字符？其余的必须恰好有两个不同字符。 - n. m.

@n.m. 我只需要一个数字，而不是包含所有满足条件的子字符串的集合。那是一个O(2^n)的问题。我认为你的方法是基于我已经拥有包含最多两个唯一字符的所有子字符串。 - Jun

当然，以下是一个示例输入和输出：输入：Hello, how are you today? 输出：你好，今天怎么样？ - Dialecticus

是的，您应该已经有一种方法来识别所有最大（即不可扩展）的长度不超过2个唯一字符的子字符串。无论如何，您需要它们来解决前两个问题。这是一个O(n)的工作。然后，您需要识别所有最大的1个唯一字符的子字符串，同样是O(n)。然后，您只需要计算有多少更小的子字符串即可。您不必识别或构建它们全部。 - n. m.

@Jun -- 看起来你可能不再需要这个了，但我已经更正了我的答案。 - Dave

Answer 1

找到所有包含两个不同字符的子字符串的数量。

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

1. 对于给定长度为len的单词，其所有子串的数量为len * (len + 1) / 2。 sum = len * (len + 1) / 2 - 我们要寻找长度大于1的子串。上述公式包括长度为1的子串。我们需要减去那些子串。

因此现在2字母子串的总数是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个唯一字符的集合生成子字符串。

我们只需要跟踪具有集合长度为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

- bsd

---

我可能误解了问题，但是这些结果对我来说看起来不正确。我会期望 "aabc" -> {"aab", "ab", "bc"}（3个，而不是5个），以及 "abcd" -> {"ab", "bc", "cd"}（3个，而不是6个）。 - Mankarse

对不起，我以为问题是要找到至少有两个唯一字符的独特子字符串。我会编辑回答。 - bsd

Answer 2

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

完整的推导说明可以在链接中找到 :)

- titan