Back To School '18: Letter Frequency

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.0s
Python 1.4s
Memory limit: 128M
Java 256M
Python 512M
Author:
Ninjaclasher
Problem types

Yunyi is given a sentence consisting of lowercase Latin letters and spaces, S, and he has to determine which language the sentence is written in. One way that he knows of determining the language is by counting letter frequencies in certain sections of the sentence.

Yunyi will give you Q queries of the form i j c, which asks for the frequency of letter c between indices i and j (inclusive) (1 \le i \le j \le |S|). Note that spaces ( ) are not considered letters, and therefore will not be queried.

Input Specification

The first line will contain the sentence S (1 \le |S| \le 10^6).

The second line will contain the integer Q (1 \le Q \le 10^5).

The next Q lines will each contain a valid query as defined above.

The sentence will only consist of lowercase Latin characters and spaces. There will only be one space between any 2 words, and there will be no leading/trailing spaces.

Output Specification

For each query, print the frequency of the letter c between indices i and j (inclusive).

Constraints

Subtask 1 [10%]

|S|, Q \le 1\,000

Subtask 2 [90%]

No additional constraints.

Sample Input

this is a very interesting sentence and you will agree
4
1 4 h
6 6 p
15 26 t
1 54 e

Sample Output

1
0
2
8

Comments


  • 1
    inoo  commented on Jan. 23, 2024, 4:25 a.m.

    ten thousand grams of pure caffeine aint cutting it 🧋🧋🧋


  • 4
    BalintR  commented on Aug. 29, 2022, 7:48 p.m.

    Since the original test data was weak, 7 new cases were added and all submissions rejudged.


  • 2
    JimmyDeng12345  commented on Sept. 17, 2018, 4:07 a.m.

    Any strategy to speed the code up? I can only get 10 out of 100. Is a memory system the way to go?


    • 4
      kingW3  commented on Sept. 17, 2018, 12:53 p.m.

      Aim for constant time queries, right now you have linear queries in i,j.