查找有效子串的数量

Question

给定一个长度为n的字符串，我想计算有多少个可能具有以下特征的子串：

a) substring length is even b) there exists a character in this substring whose frequency is equal to half the length of substring.

示例

s="idafddfi", output = 13

**说明：**

The valid substrings are: "id", "da", "af", "fd", "df", "fi", "dafd", "afdd", "fddf", "ddfi", "dfii", "idafdd", "dafddf" 

限制：

1 <= n <= 10 power 5 

s consists of lowercase english alphabets only 

public class Main {

    public static long solve(String s) {
        int n = s.length();
        long result = 0;
    
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'a']++;
                int len = j - i + 1;
                // Only check even-length substrings
                if (len % 2 == 0) {
                    if (isValid(freq, len)) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
    
    private static boolean isValid(int[] freq, int len) {
        int half = len / 2;
        for (int count : freq) {
            if (count == half) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        String s1 = "aaaaid";
        String s2 = "aidfg";
        String s3 = "ababbab";
    
        System.out.println(solve(s1)); // Output: 3
        System.out.println(solve(s2)); // Output: 4
        System.out.println(solve(s3)); // Output: 8
    }

}

我的代码运行时间复杂度为 O(n^2)，我想降低这个时间复杂度，在更短的时间内解决这个问题的正确方法是什么。

Answer 1

迭代字符串时，跟踪每个字符的累积频率。在每个索引

r

，对于 26 个可能的字符中的每一个，我们都在寻找较低的索引

l

，使得

cnt[r] - cnt[l] = (r - l) / 2

（其中

cnt[i]

表示当前字符到索引

i

的累积频率） 。由于我们只想处理整数，因此我们将其重写为

2 * (cnt[r] - cnt[l]) = r - l

。这进一步重新排列为

2 * cnt[r] - r = 2 * cnt[l] - l

。因此，我们可以跟踪映射中每个字符的每个索引处的每个

cnt[i] - i

的计数，并在每次迭代中查找具有相同

cnt[i] - i

的先前索引的数量。

我们还必须考虑仅包含两个频率相同的字符的字符串，需要将其减去以避免计数过多。实现此目的的一种方法是同时维护每个索引处字符对的

cnt[i] - i

计数。