HELP Determine the K^th character in the concatenated string

Revision en2, by ShashwatS1, 2021-06-01 06:15:22

Given a list that contains N strings of lowercase English alphabets. Any number of contiguous strings can be found together to form a new string. The grouping function accepts two integers X and Y and concatenates all strings between indices X and Y (inclusive) and returns a modified string in which the alphabets of the concatenated string are sorted.

You are asked Q questions each containing two integers L and R. Determine the K th. character in the concatenated string if we pass L and R to the grouping function.

Note: It is always guaranteed that the Kth position is valid

Input Format

  • First Line: N(number of strings in the list)
  • Next N lines: String s_i
  • Next line Q(number of questions)
  • Next Q lines : Three space-separated integers L, R and K

Output Format

For each question, print the K th character of the concatenated string in a new line.

Sample Test Cases

Sample Input

  • 5
  • aaaaa
  • bbbb
  • cccccd
  • eeeee
  • ddddd
  • 3
  • 3 3 3
  • 1 5 16
  • 3 5 15

Sample Output

  • c
  • d
  • e

Explanation

  • Q1 Grouped String cccccd. 3rd character is c
  • Q2 Grouped String aaaaabbbbcccccddddddeeeee. 16th character is d
  • Q3 Grouped String cccccddddddeeeee. 15th character is e

Input

  • 5
  • zpqrs
  • efghi
  • jklmn
  • abcde
  • 2
  • 3 3 3
  • 1 5 6

Output

  • g
  • f

Solution of this problem with complexity O(NQ) is trivial. Is it possible to solve this question with complexity better than O(NQ)

Tags #string, #hashing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ShashwatS1 2021-06-01 06:15:22 52
en1 English ShashwatS1 2021-06-01 06:05:55 1853 Initial revision (published)