Matching Ends per Range

Medium

You get a string text of lowercase English letters and a list of queries ranges. A query [l, r] selects the piece text[l..r] (both ends inclusive, 0-based). Call a non-empty substring *matching-ended* if its first and last characters are equal. Any single-character substring is matching-ended. For each query, count the matching-ended substrings inside its piece. Substrings at different positions count separately even if their text is the same. Return the answers in query order.

Example 1

text="banana", ranges=[[0, 5], [1, 3], [2, 2]] → [10, 4, 1]

In "banana" the letter a occurs 3 times (3·4/2 = 6 pieces), n twice (3 pieces) and b once (1 piece), 10 in total. "ana" gives 3 + 1 = 4, and a single letter gives 1.

Example 2

text="abba", ranges=[[0, 3]] → [6]

The matching pieces are "a", "b", "b", "a", "bb" and "abba" itself: 6 pieces.

Constraints

2 ≤ len(text) ≤ 3·10⁴
text consists of lowercase English letters
1 ≤ len(ranges) ≤ 3·10⁴
ranges[i] = [l, r], 0 ≤ l ≤ r < len(text)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table String Counting Prefix Sum

Similar problems

Pump Rods at Their Peak Hard Most Searched Words Medium Domain Visit Rollup Medium Palindrome After a Few Fixes Medium Ranking Finalists by Jury Ballots Medium

Input

text="banana", ranges=[[0, 5], [1, 3], [2, 2]]

Expected

[10, 4, 1]

Run checks the first 3 tests in your browser. Submit checks all 64 tests on the server, hidden ones included.