当前位置：首页 > article >正文

leetcode_828_统计子串中的唯一字符

article 2025/1/29 14:11:40

题意：所有子串中单个字符出现的次数和

在这里插入图片描述

问题转化：对于串中的每个字符，只包含其一次的所有子串的个数和

在这里插入图片描述

关于求只包含某位置字符一次的子串个数

在这里插入图片描述

class Solution {
public:
    int uniqueLetterString(string s) {
        /* 
        ...A...A...A...
        */
       int n = s.size();
       vector<int> alpha(26, -1);
       vector<int> leftBound(n, -1); // 记录每个位置的左端点
       for(int i = 0; i < n; i++)
       {
           leftBound[i] = alpha[s[i] - 'A'];
           alpha[s[i] - 'A'] = i;
       }

       std::fill(alpha.begin(), alpha.end(), n);
       vector<int> rightBound(n, n); // 记录每个位置的右端点
       for(int i = n - 1; i >= 0; i--)
       {
           rightBound[i] = alpha[s[i] - 'A'];
           alpha[s[i] - 'A'] = i;
       }

       int ret = 0;
       for(int i = 0; i < n; i++)
       {
           ret += (i - leftBound[i]) * (rightBound[i] - i);
       }
       return ret;
        
    }
};