Optimize Performance challenge 'Vinay Queried '

Question

Input:

The first line contains N denoting the length of Target String. This line is followed by the Target String. The Target String is followed by an integer Q denoting the number of queries asked. After this Q lines follow each line containing a Query String.

Output:

For each query output the total number of distinct Cruel Pairs that satisfies the given conditions.

Constraints:

\$1 \le N \le 5000\$

\$1 \le Q \le 10^4\$

Sum of Lengths of all Query Strings \$\le\$ 106

All strings are composed only of '0' - '9'

SAMPLE INPUT

5
75201
5
78945884875
22
00048
77
501

SAMPLE OUTPUT

0
8
8
6
5    

Explanation

Query String 1 : No such Pair exist.

Query String 2 : Pairs are (1,2) , (1,3) , (1,4) , (1,5) , (2,3) , (2,4) , (2,5) , (3,5)

Query String 5 : Pairs are (1,3) , (1,4) , (1,5) , (2,4) , (2,5)

Time Limit:1.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

FUll question: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting-problem-optimization

Code:

def get_all_substrings(input_string, length):
    return [int(input_string[i:j + 1]) for i in xrange(length) for j in xrange(i, length)]


N = int(raw_input())

target = raw_input()

target_subsets = get_all_substrings(target, N)
target = int(target)

Q_N = int(raw_input())

queries_list=[]
output=[]

for x in xrange(Q_N):
    queries_list.append(int(raw_input()))

for x in queries_list:
    if x > target:
        print 0
        continue
    cruel_pairs = sum(i>x for i in target_subsets)
    print cruel_pairs

Answer 1

Target string could be 5000 digits strong. It means that the target_subsets can have up to 12500000 elements. It is huge (I am surprised that the memory limit was not exceeded). You scan all of them for each query. Time limit exceeded obviously.

One obvious improvement is to sort target_subsets, and look for a lower bound of a query value (in logarithmic time). The result is simply len(target_subsets) - lower_bound.

This is still suboptimal, because the way you compute target_subsets has \$O(N^3)\$ time complexity. It is another candidate for TLE. It is more or less trivial to reduce it to \$(N^2)\$, but I'd still be uncomfortable.

The solution is a simple linear scan, along the lines of

Let `d` be a first non-zero digit of a query string
For target digit 't' at index 'i'
    if t > d, there are `len(target_string) - len(query) - i` pairs (as long as it is positive);
    if t == d, there _may_ produce one extra pair;
    it 0 < t < d, there are `len(target_string) - len(query) - i - 1` pairs (again, as long as it is positive);
    if t == 0, there are as many pairs as for the next non-zero digit.