Optimize Performance challenge 'Vinay Queried ' 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 &gt; target:
        print 0
        continue
    cruel_pairs = sum(i&gt;x for i in target_subsets)
    print cruel_pairs
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 &gt; 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 &lt; t &lt; 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.