2955. Number of Same-End Substrings 🔒

Description

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].

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

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.

 

Example 1:

Input: s = "abcaab", queries = [[0,0],[1,4],[2,5],[0,5]]
Output: [1,5,5,10]
Explanation: Here is the same-end substrings of each query:
1st query: s[0..0] is "a" which has 1 same-end substring: "a".
2nd query: s[1..4] is "bcaa" which has 5 same-end substrings: "bcaa", "bcaa", "bcaa", "bcaa", "bcaa".
3rd query: s[2..5] is "caab" which has 5 same-end substrings: "caab", "caab", "caab", "caab", "caab".
4th query: s[0..5] is "abcaab" which has 10 same-end substrings: "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab", "abcaab".

Example 2:

Input: s = "abcd", queries = [[0,3]]
Output: [4]
Explanation: The only query is s[0..3] which is "abcd". It has 4 same-end substrings: "abcd", "abcd", "abcd", "abcd".

 

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

Solutions

Solution 1: Prefix Sum + Enumeration

We can preprocess the prefix sum for each letter and record it in the array \(cnt\), where \(cnt[i][j]\) represents the number of times the \(i\)-th letter appears in the first \(j\) characters. In this way, for each interval \([l, r]\), we can enumerate each letter \(c\) in the interval, quickly calculate the number of times \(c\) appears in the interval \(x\) using the prefix sum array. We can arbitrarily choose two of them to form a tail-equal substring, the number of substrings is \(C_x^2=\frac{x(x-1)}{2}\), plus the situation where each letter in the interval can form a tail-equal substring alone, there are \(r - l + 1\) letters in total. Therefore, for each query \([l, r]\), the number of tail-equal substrings that meet the conditions is \(r - l + 1 + \sum_{c \in \Sigma} \frac{x_c(x_c-1)}{2}\), where \(x_c\) represents the number of times the letter \(c\) appears in the interval \([l, r]\).

The time complexity is \(O((n + m) \times |\Sigma|)\), and the space complexity is \(O(n \times |\Sigma|)\). Here, \(n\) and \(m\) are the lengths of the string \(s\) and the number of queries, respectively, and \(\Sigma\) represents the set of letters appearing in the string \(s\), in this problem \(|\Sigma|=26\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def sameEndSubstringCount(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        cs = set(s)
        cnt = {c: [0] * (n + 1) for c in cs}
        for i, a in enumerate(s, 1):
            for c in cs:
                cnt[c][i] = cnt[c][i - 1]
            cnt[a][i] += 1
        ans = []
        for l, r in queries:
            t = r - l + 1
            for c in cs:
                x = cnt[c][r + 1] - cnt[c][l]
                t += x * (x - 1) // 2
            ans.append(t)
        return ans

class Solution {
    public int[] sameEndSubstringCount(String s, int[][] queries) {
        int n = s.length();
        int[][] cnt = new int[26][n + 1];
        for (int j = 1; j <= n; ++j) {
            for (int i = 0; i < 26; ++i) {
                cnt[i][j] = cnt[i][j - 1];
            }
            cnt[s.charAt(j - 1) - 'a'][j]++;
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int k = 0; k < m; ++k) {
            int l = queries[k][0], r = queries[k][1];
            ans[k] = r - l + 1;
            for (int i = 0; i < 26; ++i) {
                int x = cnt[i][r + 1] - cnt[i][l];
                ans[k] += x * (x - 1) / 2;
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> sameEndSubstringCount(string s, vector<vector<int>>& queries) {
        int n = s.size();
        int cnt[26][n + 1];
        memset(cnt, 0, sizeof(cnt));
        for (int j = 1; j <= n; ++j) {
            for (int i = 0; i < 26; ++i) {
                cnt[i][j] = cnt[i][j - 1];
            }
            cnt[s[j - 1] - 'a'][j]++;
        }
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            ans.push_back(r - l + 1);
            for (int i = 0; i < 26; ++i) {
                int x = cnt[i][r + 1] - cnt[i][l];
                ans.back() += x * (x - 1) / 2;
            }
        }
        return ans;
    }
};

func sameEndSubstringCount(s string, queries [][]int) []int {
    n := len(s)
    cnt := make([][]int, 26)
    for i := 0; i < 26; i++ {
        cnt[i] = make([]int, n+1)
    }

    for j := 1; j <= n; j++ {
        for i := 0; i < 26; i++ {
            cnt[i][j] = cnt[i][j-1]
        }
        cnt[s[j-1]-'a'][j]++
    }

    var ans []int
    for _, q := range queries {
        l, r := q[0], q[1]
        ans = append(ans, r-l+1)
        for i := 0; i < 26; i++ {
            x := cnt[i][r+1] - cnt[i][l]
            ans[len(ans)-1] += x * (x - 1) / 2
        }
    }

    return ans
}

function sameEndSubstringCount(s: string, queries: number[][]): number[] {
    const n: number = s.length;
    const cnt: number[][] = Array.from({ length: 26 }, () => Array(n + 1).fill(0));
    for (let j = 1; j <= n; j++) {
        for (let i = 0; i < 26; i++) {
            cnt[i][j] = cnt[i][j - 1];
        }
        cnt[s.charCodeAt(j - 1) - 'a'.charCodeAt(0)][j]++;
    }
    const ans: number[] = [];
    for (const [l, r] of queries) {
        ans.push(r - l + 1);
        for (let i = 0; i < 26; i++) {
            const x: number = cnt[i][r + 1] - cnt[i][l];
            ans[ans.length - 1] += (x * (x - 1)) / 2;
        }
    }
    return ans;
}

impl Solution {
    pub fn same_end_substring_count(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = s.len();
        let mut cnt: Vec<Vec<i32>> = vec![vec![0; n + 1]; 26];
        for j in 1..=n {
            for i in 0..26 {
                cnt[i][j] = cnt[i][j - 1];
            }
            cnt[(s.as_bytes()[j - 1] as usize) - (b'a' as usize)][j] += 1;
        }
        let mut ans: Vec<i32> = Vec::new();
        for q in queries.iter() {
            let l = q[0] as usize;
            let r = q[1] as usize;
            let mut t = (r - l + 1) as i32;
            for i in 0..26 {
                let x = cnt[i][r + 1] - cnt[i][l];
                t += (x * (x - 1)) / 2;
            }
            ans.push(t);
        }
        ans
    }
}

Comments