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

Question

我正在研究一系列子串问题:

给定一个字符串:

1. 查找仅包含两个具有最大长度的唯一字符的子字符串.
2. 找到包含AT MOST两个唯一字符的所有子串的数量.
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

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

编辑：我读错了问题。该解决方案查找至少具有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。从步骤 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