滴滴笔试滴滴秋招 0913

笔试时间：2025年9月13日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：答题闯关（和谐子串）

小钟有一个长度为n的全部由大写英文字母组成的字符串s。然而，这26个英文字母之间并不总是和谐相处的，有m对字母之间存在矛盾。对于某字符串t，当且仅当任意两个字符之间不存在矛盾，则称该字符串是和谐的。求s的所有连续非空子串中，有多少子串是和谐的？

输入描述

第一行有两个整数n(1 ≤ n ≤ 2×10^5)、m(0 ≤ m ≤ 500)，分别表示字符串s的长度和存在矛盾的字符对的个数。第二行有一行字符串s。接下来m行第i行有两个字符ch_{i,1}、ch_{i,2}，表示字符ch_{i,1}与字符ch_{i,2}之间存在矛盾。

输出描述

输出一个数字，表示s的多少连续子串是和谐的。

样例输入

4 1

ACBA

A B

样例输出

6

样例说明：样例中一共有10个子串：A、C、B、A、AC、CB、BA、ACB、CBA、ACBA，其中共有6个子串满足不同时出现A和B。

参考题解

解题思路：

使用滑动窗口（双指针）技术。用26×26的布尔矩阵标记矛盾关系，维护窗口[l,r]内每个字母出现次数。当尝试把新字符放入窗口时，检查是否与窗口中已存在的字母矛盾。如果矛盾，就不断右移左端直到矛盾消失。此时窗口[l,r]是以r结尾的最长和谐子串，以r结尾的和谐子串数量为r-l+1。

C++：

#include <bits/stdc++.h>
using namespace std;

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    string S;
    cin >> S;
    
    bool bad[26][26] = {};
    for (int i = 0; i < M; i++) {
        string ca, cb;
        cin >> ca >> cb;
        int ia = ca[0] - 'A';
        int ib = cb[0] - 'A';
        bad[ia][ib] = bad[ib][ia] = true;
    }
    
    int freq[26] = {};
    long long res = 0;
    int L = 0;
    
    for (int R = 0; R < N; R++) {
        int c = S[R] - 'A';
        while (true) {
            bool ok = true;
            for (int t = 0; t < 26; t++) {
                if (bad[c][t] && freq[t] > 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) break;
            int oldc = S[L] - 'A';
            freq[oldc]--;
            L++;
        }
        freq[c]++;
        res += (R - L + 1);
    }
    
    cout << res << "\n";
}

int main() {
    solve();
    return 0;
}

Java：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        String S = sc.next();
        
        boolean[][] bad = new boolean[26][26];
        for (int i = 0; i < M; i++) {
            String ca = sc.next();
            String cb = sc.next();
            int ia = ca.charAt(0) - 'A';
            int ib = cb.charAt(0) - 'A';
            bad[ia][ib] = bad[ib][ia] = true;
        }
        
        int[] freq = new int[26];
        long res = 0;
        int L = 0;
        
        for (int R = 0; R < N; R++) {
            int c = S.charAt(R) - 'A';
            while (true) {
                boolean ok = true;
                for (int t = 0; t < 26; t++) {
                    if (bad[c][t] && freq[t] > 0) {
                        ok = false;
                        break;
                    }
                }
                if (ok) break;
                int oldc = S.charAt(L) - 'A';
                freq[oldc]--;
                L++;
            }
            freq[c]++;
            res += (R - L + 1);
        }
        
        System.out.println(res);
        sc.close();
    }
}

Python：

def solve():
    N, M = map(int, input().split())
    S = input()
    
    bad = [[False] * 26 for _ in range(26)]
    for _ in range(M):
        ca, cb = input().split()
        ia = ord(ca) - ord('A')
        ib = ord(cb) - ord('A')
        bad[ia][ib] = bad[ib][ia] = True
    
    freq = [0] * 26
    res = 0
    L = 0
    
    for R in range(N):
        c = ord(S[R]) - ord('A')
        while True:
            ok = True
            for t in range(26):
                if bad[c][t] and freq[t] > 0:
                    ok = False
                    break
            if ok:
                break
            oldc = ord(S[L]) - ord('A')
            freq[oldc] -= 1
            L += 1
        
        freq[c] += 1
        res += (R - L + 1)
    
    print(res)

solve()