Skip to content

2955. Number of Same-End Substrings 👍

  • Time: $O(26n + q)$
  • Space: $O(26n + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  vector<int> sameEndSubstringCount(string s, vector<vector<int>>& queries) {
    vector<int> ans;
    vector<int> count(26);
    // counts[i] := the count of s[0..i)
    vector<vector<int>> counts = {count};

    for (const char c : s) {
      ++count[c - 'a'];
      counts.push_back(count);
    }

    for (const vector<int>& query : queries) {
      const int l = query[0];
      const int r = query[1];
      int sameEndCount = 0;
      for (char c = 'a'; c <= 'z'; ++c) {
        //   the count of s[0..r + 1) - the count of s[0..l)
        // = the count of s[l..r]
        const int freq = counts[r + 1][c - 'a'] - counts[l][c - 'a'];
        //   C(freq, 2) + freq
        // = freq * (freq - 1) / 2 + freq
        // = freq * (freq + 1) / 2
        sameEndCount += freq * (freq + 1) / 2;
      }
      ans.push_back(sameEndCount);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int[] sameEndSubstringCount(String s, int[][] queries) {
    int[] ans = new int[queries.length];
    int[] count = new int[26];
    // counts[i] := the count of s[0..i)
    int[][] counts = new int[s.length() + 1][26];

    for (int i = 0; i < s.length(); i++) {
      ++count[s.charAt(i) - 'a'];
      System.arraycopy(count, 0, counts[i + 1], 0, 26);
    }

    for (int i = 0; i < queries.length; ++i) {
      final int l = queries[i][0];
      final int r = queries[i][1];
      int sameEndCount = 0;
      for (char c = 'a'; c <= 'z'; ++c) {
        //   the count of s[0..r + 1) - the count of s[0..l)
        // = the count of s[l..r]
        final int freq = counts[r + 1][c - 'a'] - counts[l][c - 'a'];
        //   C(freq, 2) + freq
        // = freq * (freq - 1) / 2 + freq
        // = freq * (freq + 1) / 2
        sameEndCount += freq * (freq + 1) / 2;
      }
      ans[i] = sameEndCount;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def sameEndSubstringCount(
      self,
      s: str,
      queries: list[list[int]],
  ) -> list[int]:
    count = collections.Counter()
    # counts[i] := the count of s[0..i)
    counts = [count.copy()]

    for c in s:
      count[c] += 1
      counts.append(count.copy())

    ans = []

    for l, r in queries:
      sameEndCount = 0
      for c in string.ascii_lowercase:
        #   the count of s[0..r] - the count of s[0..l - 1]
        # = the count of s[l..r]
        freq = counts[r + 1][c] - counts[l][c]
        #   C(freq, 2) + freq
        # = freq * (freq - 1) / 2 + freq
        # = freq * (freq + 1) / 2
        sameEndCount += freq * (freq + 1) // 2
      ans.append(sameEndCount)

    return ans