[Leetcode 2955번 문제]2955. Number of Same-End Substrings

문제 상황

You are given a 0-indexed string s, and a 2D array of integers queries, where queries[i] = [li, ri] indicates a substring of s starting from the index li and ending at the index ri (both inclusive), i.e. s[li..ri].

각각의 쿼리가 subarray

Return an array ans where ans[i] is the number of same-end substrings of queries[i].

same-end?

A 0-indexed string t of length n is called same-end if it has the same character at both of its ends, i.e., t[0] == t[n - 1].

A substring is a contiguous non-empty sequence of characters within a string.

입력

Constraints:

• 2 <= s.length <= 3 * 104
• s consists only of lowercase English letters.
• 1 <= queries.length <= 3 * 104
• queries[i] = [li, ri]
• 0 <= li <= ri < s.length

출력

시작과 끝이 같은 substring의 개수를 담은 벡터

과정

약간 prefixSum 처럼

어차피 처음과 끝이 같은 substring은 ( ) 같은 문자가 n개라면 (n)(n + 1)/2 개라고 할 수 있음

그럼 주어진 시점에서 각 문자의 개수만 안다면 총 완성되는 문자열의 개수를 알 수 있음

 

알고리즘

class Solution {
    vector<vector<int>> prefixSum;
public:
    vector<int> sameEndSubstringCount(string s, vector<vector<int>>& queries) {
        int ssz = s.length();
        prefixSum = vector<vector<int>> (ssz + 1, vector<int> (26, 0));
        for (int i = 0; i < ssz; i++)
        {
            for (int j = 0; j < 26; j++)
            {
                prefixSum[i + 1][j] = prefixSum[i][j];
            }
            prefixSum[i + 1][s[i] - 'a']++;
        }
        vector<int> answer;
        for (vector<int> query : queries)
        {
            int s = query[0], e = query[1] + 1;
            int partAns = 0;
            for (int i = 0; i < 26; i++)
            {
                int arg = prefixSum[e][i] - prefixSum[s][i];
                partAns += (arg + 1) * arg / 2;
            }
            answer.emplace_back(partAns);
        }
        return answer;
    }
};