如何通过预处理实现O(1)时间统计子串中指定字符的出现次数？

面试官提出的问题：给定字符串、目标字符，以及子串的起始（start）和结束（end）索引，统计该字符在[start, end)区间子串中的出现次数。比如示例：

String s = "abcnc";
char find = 'c';
int start = 1;
int end = 4;

子串是bcnc，其中'c'出现2次，应返回2。

初始的O(N)遍历解法如下：

int freq(String s, char c, int start, int end) {
    int result = 0; 
    for(int i = start; i < end; i++) {
        if(s.charAt(i) == c) {
            result++;
        }
    }
    return result;
}

这种方法每次查询都要遍历子串，当查询次数很多时效率很低。面试官要求通过预处理将查询时间优化到O(1)（或近似常数时间），核心思路是把预处理的时间成本分摊到多次查询上。

方案一：前缀和数组（严格O(1)查询） #

预处理逻辑 #

为每个字符维护一个前缀和数组，数组的第i位表示字符串前i个字符（即s[0..i-1]）中该字符的出现次数。比如示例字符串abcnc，字符'c'的前缀和数组是[0,0,0,1,1,2]：

• prefix[0] = 0（前0个字符，无'c'）
• prefix[1] = 0（s[0]='a'，无'c'）
• prefix[2] = 0（s[0-1]='ab'，无'c'）
• prefix[3] = 1（s[0-2]='abc'，有1个'c'）
• ...以此类推

可以用HashMap<Character, int[]>来存储每个字符的前缀和数组，避免浪费空间在未出现的字符上。

查询逻辑 #

对于区间[start, end)，目标字符的出现次数 = prefix[end] - prefix[start]，直接通过数组下标取值，时间复杂度O(1)。

代码实现 #

import java.util.HashMap;
import java.util.Map;

class CharFreqCounter {
    private Map<Character, int[]> prefixSumMap;

    // 预处理字符串，仅需执行一次
    public CharFreqCounter(String s) {
        prefixSumMap = new HashMap<>();
        int n = s.length();
        // 初始化所有出现过的字符的前缀和数组
        for (char c : s.toCharArray()) {
            if (!prefixSumMap.containsKey(c)) {
                prefixSumMap.put(c, new int[n + 1]);
            }
        }
        // 填充前缀和数组
        for (int i = 0; i < n; i++) {
            char current = s.charAt(i);
            // 复制前一位的数值，再更新当前字符的计数
            for (Map.Entry<Character, int[]> entry : prefixSumMap.entrySet()) {
                entry.getValue()[i + 1] = entry.getValue()[i];
            }
            prefixSumMap.get(current)[i + 1]++;
        }
    }

    // O(1)时间查询
    public int freq(char c, int start, int end) {
        if (!prefixSumMap.containsKey(c)) {
            return 0;
        }
        int[] prefix = prefixSumMap.get(c);
        // 处理边界：如果start>=end或超出字符串范围返回0
        if (start >= end || start < 0 || end > prefix.length - 1) {
            return 0;
        }
        return prefix[end] - prefix[start];
    }
}

// 使用示例
public class Main {
    public static void main(String[] args) {
        String s = "abcnc";
        CharFreqCounter counter = new CharFreqCounter(s);
        System.out.println(counter.freq('c', 1, 4)); // 输出2
    }
}

方案二：记录字符索引+二分查找（近似O(1)查询） #

预处理逻辑 #

用HashMap<Character, List<Integer>>存储每个字符出现的所有索引位置。比如示例字符串abcnc中，'c'对应的列表是[2, 4]（字符串索引从0开始）。

查询逻辑 #

要找区间[start, end)内的字符个数，等价于在列表中找大于等于start且小于end的元素数量。可以通过二分查找快速定位：

• 找到第一个>=start的元素下标（left）
• 找到第一个>=end的元素下标（right）
• 结果就是right - left，时间复杂度是O(logM)（M是目标字符的出现次数），当M不大时近似于常数时间。

代码实现 #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Collections;

class CharIndexCounter {
    private Map<Character, List<Integer>> charIndicesMap;

    // 预处理字符串，仅需执行一次
    public CharIndexCounter(String s) {
        charIndicesMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            charIndicesMap.computeIfAbsent(c, k -> new ArrayList<>()).add(i);
        }
    }

    // 近似O(1)查询（实际O(logM)）
    public int freq(char c, int start, int end) {
        List<Integer> indices = charIndicesMap.get(c);
        if (indices == null || indices.isEmpty()) {
            return 0;
        }
        // 找第一个>=start的位置
        int left = Collections.binarySearch(indices, start);
        left = left < 0 ? -left - 1 : left;
        // 找第一个>=end的位置
        int right = Collections.binarySearch(indices, end);
        right = right < 0 ? -right - 1 : right;
        return right - left;
    }
}

// 使用示例
public class Main {
    public static void main(String[] args) {
        String s = "abcnc";
        CharIndexCounter counter = new CharIndexCounter(s);
        System.out.println(counter.freq('c', 1, 4)); // 输出2
    }
}

两种方案对比 #

• 前缀和数组：查询严格O(1)，但空间复杂度是O(N*K)（K是出现的字符种类数），适合字符种类少、查询次数极多的场景。
• 索引列表+二分：空间复杂度O(N)（仅存储字符出现的索引），查询接近常数时间，适合字符种类多但单个字符出现次数少的场景。

内容的提问来源于stack exchange，提问作者Matt_00