Reslan's blog

help with this problem
By Reslan, history, 10 years ago, In English

Hello everyone :D I'm given a string s of length n , letters could be uppercase or lowercase. and I need to answer a query of the type : given ( left , right ) ( where left <= right ) count the number of distinct letters in the range [ left , right ] , for example if s = bcAAcbc , n = 7 , query( 0 , 2 ) = 3 , query( 2 , 3 ) = 1, NOTE : by distinct I mean either different letters , or the same letter but the first one is uppercase and the second is lowercase , for instance a and A are distinct , a and b also distinct , A and A are NOT could this problem be solved using segment tree ? thank in advance :D

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi :) are the queries all given before-hand ? (is the question off-line, in other words)

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Populate an array pre[][] , where pre[i][j] denotes the number of occurrences of character j among the first i characters of your string,

Now, Each query can be answered using 52 iterations. For each character you need to check whether it exists in the range or not. Any character c exists in this subarray, if pre[right][c] - pre[left - 1][c] > 0. Output the count of all characters that exists in this range.

→ Reply
»
10 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

Indeed, we can solve it with a segment tree, with complexity O(n * log(n)), since the alphabet size is smaller than 64. First, instead of having the string be made up of 'a', ..., 'z', 'A', ..., 'Z', let's say that the string is made of numbers 1, ..., 26+26 = 52. Now, let's build a segment tree in which, for each node, we store a 64 bit integer. The i'th binary digit of the integer is 1 if the number i appears in the segment associated with the node, otherwise it is 0. Obviously, if a node is associated with a one element segment, then its value is 2 ^ i, where i is the number in the segment. Otherwise, if l and r are the values of the left child, respectively right child of the node, then the node will have value l | r. If the value for a query segment is v, then the result is the number of bits with value 1 in v (__builtin_popcount(v)).

→ Reply